Powered by GitBook

1. Two Sum (Easy) (ALL)

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Solution 1: Brute Force O(n^2); O(1) 未TLE

这题明显可以用暴力搜索解决：i从0开始遍历，j从i + 1开始遍历，检查nums[i]+nums[j]是否等于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 new int[]{-1, -1};
    }

Solution 2: HashMap O(n); O(n)

O(n^2)的时间复杂度肯定是不能满足面试官的要求的，所以考虑用空间换时间。
因为要求返回索引，所以我们需要一个数据结构来记录num和其索引，很自然想到用HashMap。
但是我们需要考虑下这里的key是否唯一，因为nums可能存在duplicate。
因为题目说了有且只有一个解S，那么如果nums中有重复数a，有两种情况，

a∉S，这种情况a和S无关，value随便覆盖。

S={a,a}，且这种情况下a只能出现两次，当找到第二个a时，S已经确定，不用覆盖第一个a的value。
不可能有这种情况：S={a,b}, S={a', b}，这样的话就有两个解了。所以可以认为key唯一。
这样解法就清楚了：遍历数组，用HashMap存num和其index，检查map是否存在target-nums[i]，若存在，返回结果。

    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(target - nums[i])) {
                return new int[]{map.get(target - nums[i]), i};
            }
            map.put(nums[i], i); //这行代码只能放在if下面，先检查，没找到解再存入map。
        }
        return new int[]{-1, -1};
    }

Follow Up:

two sum with duplicates 比如说｛1, 2, 2, 3｝，target = 5, 他要{(2, 3), (2, 3)｝
本质是3sum的简化版，但是要保留重复结果，下面的代码其实不太对，因为会漏一些结果，TODO
注：如果要返回distinct pairs，那就真正是3Sum的简化版了。
sort + Two Pointers O(n log n); O(1)

    public static List<List<Integer>> twoSumE(int[] nums, int target) {
        List<List<Integer>> res = new ArrayList<>();
        if (nums == null || nums.length < 2) {
            return res;
        }

        Arrays.sort(nums);
        int l = 0;
        int r = nums.length - 1;
        while (l < r) {
            if (nums[l] + nums[r] == target) {
                res.add(Arrays.asList(nums[l], nums[r]));

                while (l < r && nums[l] == nums[l + 1]) {
                    res.add(Arrays.asList(nums[l], nums[r])); //add duplicate result
                    l++;
                }
                while (l < r && nums[r] == nums[r - 1]) {
                    res.add(Arrays.asList(nums[l], nums[r]));  //add duplicate result
                    r--;
                }
                l++;
                r--;
            } else if (nums[l] + nums[r] < target) {
                l++;
            } else {
                r--;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[] nums = {1,2,2,2,3};
        System.out.println(twoSumE(nums, 5));
    }

two sum with duplicates, 返回所有的可能的index pairs

    /**
     * duplicate number, 返回所有的可能的index pairs
     * HashMap & HashSet 应该是O(n^2);O(n) 
     * 考虑极端情况，index pair的总数有O(n^2)个[1,1,1,1,1],2
     */
    public List<int[]> twoSumC(int[] nums, int target) {
        if (nums == null) {
            return null;
        }

        Map<Integer, Set<Integer>> map = new HashMap<>();
        List<int[]> res = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if (!map.containsKey(nums[i])) {
                Set<Integer> set = new HashSet<>();
                set.add(i);
                map.put(nums[i], set);
            } else {
                map.get(nums[i]).add(i);
            }

            if (map.containsKey(target - nums[i])) {
                for (Integer j : map.get(target - nums[i])) {
                    if (j != i) {
                        res.add(new int[]{j, i});
                        System.out.println(j + " " + i);
                    }
                }
            }
        }
        return res;
    }

Input array is sorted, duplicate number, 返回所有的可能的index pairs

    /**
     * Input array is sorted, duplicate number, 返回所有的可能的index pairs
     * Two Pointers O(n);O(1) 下面解法不太对，要改
     * [-1,-1,1,1] 0 result = {(0,2),(0,3),(1,2),(1,3)} 而不是{(0,3),(1,3),(1,2)}
     * set其实也用不到啊，比如你那个例子，已经知道（0,3）这个对了，然后双指针查到-1的个数是2,1的个数是2，
     * 然后写个辅助函数返回0，1和2,3的组合就行
     */
    public List<int[]> twoSumD(int[] nums, int target) {
        if (nums == null) {
            return null;
        }

        int left = 0;
        int right = nums.length - 1;
        List<int[]> res = new ArrayList<>();
        while (left < right) {
            if (nums[left] + nums[right] == target) {
                res.add(new int[]{left, right});
                System.out.println(left + " " + right);
                while (left < right && nums[left] == nums[left + 1]) {
                    left++;
                    res.add(new int[]{left, right});
                }
                while (left < right && nums[right] == nums[right - 1]) {
                    right--;
                    res.add(new int[]{left, right});
                }
            } else if (nums[left] + nums[right] < target) {
                left++;
            } else {
                right--;
            }
        }
        return res;
    }

results matching ""

No results matching ""