LeetCode No.1 两数之和

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

解法一

第一种最简单直接的想法即暴力解法，使用两个循环逐个遍历查找两数之和是否等于 target 值。

    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length-1; i++) {
            for (int j = i+1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i,j};
                }
            }
        }
        return nums;
    }

时间复杂度: O(n^2)

解法二

除此之外，应该还可以有其他的思路。比如想办法降低时间复杂度。能否少使用一次循环。使用 hashmap 的字典属性，可以实现这一点，典型的 “空间换时间”。

    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; i++) {
            int result = target - nums[i];
            if (map.containsKey(result)) {
                return new int[]{i, map.get(result)};
            } else {
                map.put(nums[i], i);
            }
        }
        return new int[]{};
    }

时间复杂度：O(n)

空间复杂度：O(n)

扩展解法三(不可用，作参考)

另外一种思路，假如我们在处理一个排序数组。那么可是使用双指针，队首队尾各一个指针，逐个递进检查队首队尾指针所指向的元素之和，是否匹配。当我用这个代码测试的时候，发现没通过的case卡在数组 [3,2,4] 上面。说明题目给出的是无序数组。所以这个解法不可用。不过这也是一种题解思路，记录在此。

    /**
     * 针对有序数组的双指针法
     * @param nums
     * @param target
     * @return
     */
    public int[] twoSum(int[] nums, int target) {
        Arrays.sort(nums);
        int head = 0;
        int tail = nums.length - 1;
        int[] ans = new int[2];
        for (int i = 0; i < nums.length; i++) {
            int sum = nums[head] + nums[tail];
            if (sum == target) {
                ans[0] = head;
                ans[1] = tail;
            }
            if (sum > target) {
                tail--;
            }
            if (sum < target) {
                head++;
            }
        }
        return ans;
    }