侧边栏壁纸
博主头像
孔子说JAVA博主等级

成功只是一只沦落在鸡窝里的鹰,成功永远属于自信且有毅力的人!

  • 累计撰写 292 篇文章
  • 累计创建 132 个标签
  • 累计收到 4 条评论

目 录CONTENT

文章目录

算法:给定一个整型数组,找出两个整数为指定整数的和

孔子说JAVA
2019-10-11 / 0 评论 / 0 点赞 / 66 阅读 / 3,211 字 / 正在检测是否收录...

1、题目

给定一个整型数组,是否能找出其中的两个数使其和为某个指定的值?(假定是无序数组)

2、解法一:暴力破解(穷举法,不提倡)

暴力破解 (穷举,时间复杂度:O(n^2),正常不会用这个,假如只是为了快速解题,对时间没有限制,用这个最简单)

/**
 * 给定一个整型数组,是否能找出其中的两个数使其和为某个指定的值?(假定是无序数组)
 * 暴力破解 (穷举,时间复杂度:O(n^2),正常不会用这个,假如只是为了快速解题,对时间没有限制,用这个最简单)
 *
 * @param nums 无序整形数组
 * @param target 和值
 */
public static void search1(int[] nums, int target) {
    int one, two;
    for (int i = 0; i < nums.length; i++) {
        one = nums[i];
        two = target - one;
        for (int j = 0; j < nums.length; j++) {
            if (i != j) {
                if (two == nums[j]) {
                    System.out.println("one:" + one + " two:" + two);
                    return;
                }
            }
        }
    }
    System.out.println("找不到这两个数");
}

3、解法二:二分法(相当于用两个指针)

两个指针二分查找–重点是先使数组有序(排序时间复杂度为O(nlog(n)),while最多O(N),所以最终程序的时间复杂度为:O(nlo(n)))

/**
 * 两个指针二分查找--重点是先使数组有序
 * (排序时间复杂度为O(nlog(n)),while最多O(N),所以最终程序的时间复杂度为:O(nlo(n)))
 * 
 * @param nums 无序整形数组
 * @param target 和值
 */
public static void search2(int[] nums, int target) {
    System.out.println("二分查找(两个指针二分查找,时间复杂度:O(nlog(n)))");
    // 1.排列(用的是Dual-Pivot Quicksort(快速排序),时间复杂度为O(nlog(n)))
    // ****此处是重点****
    Arrays.sort(nums);
    // 2.类二分查找
    int left = 0;
    int right = nums.length - 1;
//  for(;left < right;) 
    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum == target) {
            System.out.println("one:" + nums[left] + " two:" + nums[right]);
            return;
        }
        if (sum < target) {// 太小 left增加
            left++;
        }
        if (sum > target) {// 太大 right减少
            right--;
        }
    }
    System.out.println("找不到这两个数");
}

4、解法三:使用哈希表和辅助空间

使用辅助空间(使用哈希表,时间复杂度是O(n),空间复杂度:O(n),n是数组大小),把数值作为 key,它的下标作为 value 遍历数组,判断 map 是否含有这个目标值-当前数值,有直接返回,没有的话放到map里面。

/**
 * 使用辅助空间(使用哈希表,时间复杂度是O(n),空间复杂度:O(n),n是数组大小)
 * 把数值作为 key,它的下标作为 value 遍历数组,判断 map 是否含有这个目标值-当前数值, 有直接返回,没有的话放到map里面
 *
 * 所以以后写代码,如果有双层 for 循环,首先考虑一下能否用 map 替换一层
 * 
 * 空间换时间的方式,用hashmap来记录值和index,这样只要遍历一遍,并用Hashmap直接判定是否存在另一个下标。
 * 这种方法有一个问题,就是当存在相同值时,并且恰好求和的两个数是同值不同位时,必然会出问题。修正方式是
 * hashmap中的value用list或者set来存储,那么如果最终两个值对应的index set不同,或者index set相同但set
 * size>1,那么就是存在。
 */
public static void search3(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        if (map.containsKey(target - nums[i])) {
            System.out.println("one:" + nums[i] + " two:" + (target - nums[i]));
            return;
        }
        map.put(nums[i], i);
    }
    System.out.println("找不到这两个数");
}

5、拓展题目

设计一个类,包含如下两个成员函数(允许整数集合中存在相同值的元素):

  1. save(int input) 插入一个整数到一个整数集合里。
  2. test(int target) 检查是否存在两个数和为输入值。如果存在着两个数,则返回true,否则返回false
import java.util.HashMap;
import java.util.Iterator;

/**
 * 设计一个类,包含如下两个成员函数(允许整数集合中存在相同值的元素): 
 * save(int input) 插入一个整数到一个整数集合里。 
 * test(int target) 检查是否存在两个数和为输入值。如果存在着两个数,则返回true,否则返回false 
 * 
 * @author kongshubin
 *
 */
public class TwoNumberOfSum {
    // key:数值,value:数值对应的个数
    HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();

    /**
     * 插入一个整数到一个整数集合里
     * 
     * @param input
     */
    public void save(int input) {
    	int count = 0;
    	if (map.containsKey(input)) {
    		count = map.get(input);
    	}
    	map.put(input, count + 1);
    }

    /**
     * 检查是否存在两个数和为输入值
     * 
     * @param target
     * @return 如果存在着两个数,则返回true,否则返回false
     */
    public boolean test(int target) {
    	Iterator<Integer> iterator = map.keySet().iterator();
    	while (iterator.hasNext()) {
            int one = iterator.next();
            int two = target - one;
            if (map.containsKey(two)) {
                System.out.println("one:" + one + " two:" + two);
                if (!(target == two << 1 && map.get(two) == 1)) {
                    // 如果target为two的2倍,并且只有一个two不同时成立,返回true
                    return true;
                }
            }
    	}
    	return false;
    }

    public static void main(String[] args) {
    	TwoNumberOfSum t = new TwoNumberOfSum();
    	t.save(5);
    	t.save(10);
    	t.save(4);
    	t.save(7);
    	System.out.println(t.test(12));
    }
}
0

评论区