LeetCode-1.Two Sum.md

LeetCode - 1. Two Sum(Hash)

题目链接

https://leetcode.com/problems/two-sum/

题目

暴力方法就不说了。这题用Hash(O(N))或者双指针O(N*logN)。

一、方法一

时间复杂度2 * O(N)。

• 先遍历一边数组，使用HashMap存储每个数的下标；
• 然后再遍历一遍数组，寻找target - nums[i]在map中存不存在，如果存在且对应的值不等于当前的下标i(即目标元素不能是nums[i]本身)，就说明存在解，返回两个下标即可；

图:

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < nums.length; i++) map.put(nums[i], i); 
        for(int i = 0; i < nums.length; i++){
            int val = target - nums[i];
            if(map.containsKey(val) && map.get(val) != i)
                return new int[]{i, map.get(val)};
        }
        throw new RuntimeException("No such solution!");
    }
}

---

二、方法二

时间复杂度O(N)。

在检查完当前元素num[i]之后(检查target - nums[i])。

再顺便将{nums[i], i}放入哈希表，因为当前放入的元素后面还会回过头来检查这个元素是否是目标元素。

图:

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < nums.length; i++){
            int val = target - nums[i];
            if(map.containsKey(val)) // 肯定不会map.get(val) == i 
                return new int[]{i, map.get(val)};
            map.put(nums[i], i);
        }
        throw new RuntimeException("No such solution!");
    }
}

类似的进阶问题。

三、排序双指针

这个方法时间复杂度是排序的时间，即N*logN。

思想就是，使用两个指针，从两边往中间靠拢，这个原理是基于数组已经排序了。因为如果当前nums[L] + nums[R] < target，那我只能增加nums[L]才有可能去达到target，所以L++，类似，如果nums[L] + nums[R] > target，我们就R--。

由于我们需要返回的是两个元素的下标，所以我们还需要存储原来数据的下标的位置。我们可以构造一个结构体，然后对值val排序，最后找到的时候，返回对应的原来的下标即可。

class Solution {

    class Pair {
        int id;
        int val;

        public Pair(int id, int val) {
            this.id = id;
            this.val = val;
        }
    }

    public int[] twoSum(int[] nums, int target) {
        Pair[] pairs = new Pair[nums.length];
        for (int i = 0; i < nums.length; i++)
            pairs[i] = new Pair(i, nums[i]);
        Arrays.sort(pairs, (o1, o2) -> o1.val - o2.val);//按照值排序
        int L = 0, R = nums.length - 1;
        while (L < R) {
            if (pairs[L].val + pairs[R].val == target)
                return new int[]{pairs[L].id, pairs[R].id};
            else if (pairs[L].val + pairs[R].val < target)
                L++;
            else
                R--;
        }
        throw new RuntimeException("No such solution!");
    }
}