使用三种算法来解决Two-Sum问题

发表于 更新于 分类于
学习笔记

两数之和

在给定的数组内, 求其中两个数是否和给定的一个数相等

例

1
2
3
4
5
6
// 判断nums中某两个数相加是否等于target

// 给定的数组
static int[] nums = new int[]{2, 4, 6, 7, 1};
// 目前求和的数字
static int target = 10;

算法1

1
2
3
4
5
6
7
8
9
10
11
public boolean twoSum(int[] nums, int tg) {
    int size = nums.length;
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] + nums[j] == tg) {
                return true;
            }
        }
    }
    return false;
}

解释

size是nums的长度, 也就是5, 那第一个循环中, i的值为0~4
第二个循环中, j为i的前面的所有值

  1. i=0(数组中为2), j不存在
  2. i=1(数组中为4), j=0(数组中为2)
  3. i=2(数组中为6),j=0(数组中为2),1(数组中为4), 此时(j=1)+(i=2)等于target(10)
    …
    也就是第一层循环遍历每一层, 第二层循环依次拿之前的数字和当前数字进行相加比较

算法2

1
2
3
4
5
6
7
8
9
10
public boolean twoSum(int[] nums, int tg) {
    Set set = new HashSet();
    for (int i : nums) {
        if (set.contains(tg - i)) {
            return true;
        }
        set.add(i);
    }
    return false;
}

解释

使用一个记事本, 记录下获取过的数值
使用目标值target减去数组中的每一个, 判断差是否在集合中, 如果存在则返回正确, 不存在则把减去的值放入该集合中, 依次进行判断;

算法3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public boolean twoSum(int[] nums, int tg) {
    Arrays.sort(nums);
    int left = 0, right = nums.length - 1;
    while (left < right) {
        if (nums[left] + nums[right] == tg) {
            return true;
        } else if (nums[left] + nums[right] > tg) {
            right--;
        } else {
            left++;
        }
    }
    return false;
}

解释

先把数组做升序排序(会影响left和right的移动), 然后把收尾进行相加, 如果大于target值, 则把right的位置向前移动, 如果小于target值, 则把left值向后移动