1. Two Sum

一刷

神他妈2sum
原题竟然是第一次写。。。感觉自己想的有点神奇结果发现答案就是差不多这么写的
因为是2sum 所以如果排序用2pointer的话 O(nlogn)是leading term 不是特别的efficient
于是选择了HashMap

57.83 %
public class Solution {
    public int[] twoSum(int[] nums, int target) {
        //key-expected value, value-index
        if (nums == null || nums.length <= 1) return new int[0];
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])) {
                return new int[]{map.get(nums[i]), i};
            }
            map.put(target - nums[i], i);
        }
        return new int[0];
    }
}

二刷

这道题没有办法用Arrays.sort() 加双指针的方法， 因为要求return的是index

sort会打乱原来的index

除非建立自己的tuple, 然后sort tuple

Version #1 HashMap

Time O(n)

Space O(n)

Runtime: 4 ms, faster than 68.51% of Java online submissions for Two Sum.

Memory Usage: 45.9 MB, less than 28.04% of Java online submissions for Two Sum.

class Solution {

    public int[] twoSum(int[] nums, int target) {

        // Scan the array and put the {target-nums[i], i} in a hashmap

        // Check if there exists a key of nums[i] in the hashmap

        if (nums == null || nums.length < 2) {

            return new int[0];

        }

        Map<Integer, Integer> hash = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {

            int j = hash.getOrDefault(nums[i], -1);

            if (j != -1) {

                return new int[]{j, i};

            }

            hash.put(target - nums[i], i);

        }

        return new int[0];

    }

}