1、两数之和

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。示例:

给定 nums = [2, 7, 11, 15], target = 9因为 nums[0] + nums[1] = 2 + 7 = 9所以返回 [0, 1]

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/two-sum

1、暴力解

暴力解，没什么说的，两层循环，每两个数相加判断是否等于target。

1
2
3
4
5
6
7
8
9
10
11
12
13
public static int[] twoSum1(int[] nums, int target) {
    int[] result = new int[2];
    for (int i = 0; i < nums.length - 1; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if ((nums[i] + nums[j]) == target) {
                result[0] = i;
                result[1] = j;
                return result;
            }
        }
    }
    return result;
}

2、一遍哈希表(官方解法)

这个方法本质上是：拟定数组的当前下标的值为两数之中的一个数，然后去找另一个数，如果找不到则下一个数继续这么找，直到最后。

1
2
3
4
5
6
7
8
9
10
11
public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement)) {
            return new int[] { map.get(complement), i };
        }
        map.put(nums[i], i);
    }
    throw new IllegalArgumentException("No two sum solution");
}

3、数组解法

数组为排序数组从两边同时遍历数组，两数加和判断是否为target，如果小于target，则头指针加1，如果大于target尾指针加1，直到两指针相遇。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static int[] twoSum(int[] nums, int target) {
    int[] result = {0, 0};
    int a;
    int i = 0, j = nums.length - 1;
    while (i < j) {
        a = nums[i] + nums[j];
        if (a == target) {
            result[0] = i;
            result[1] = j;
        } else if (a > target) {
            j--;
        } else {
            i++;
        }
    }
    return result;
}