LeetCode Two Sum&Two Sum II - Input array is sorted&3Sum&4Sum 一锅煮题解

文章目录

Two Sum
Two Sum II
3Sum
4Sum

Two Sum

题意

给定一个数组，和指定一个目标和。从数组中选择两个数满足和为目标和。保证有且只有一个解。每个元素只可以用一次。
思路

Hash表快速查询值是否在数组中存在。

枚举一个数，查询另一个数是否存在。

注意：虽然一个元素只可以使用一次，但是数组中可以出现重复的元素。
复杂度

T(N)=O(N),M(N)=O(N)T(N)=O(N),M(N)=O(N)T(N)=O(N),M(N)=O(N)
结果

Runtime: 5 ms, faster than 70.02% of Java online submissions for Two Sum.

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

即(5ms, 70.02%, 37.5MB, 100.0%)
源码

class Solution {

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

        int []ans = new int[2];

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

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

            if (m.containsKey(nums[i])) {

                if (nums[i]*2 == target) {

                    ans[0] = m.get(nums[i]);

                    ans[1] = i;

                    return ans;

                }

            } else {

                m.put(nums[i], i);

            }

        }

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

            if (nums[i]*2 != target && m.containsKey(target-nums[i])) {

                ans[0] = i;

                ans[1] = m.get(target-nums[i]);

                break;

            }

        return ans;

    }

}

Two Sum II

题意

题意不变。只是输入数组有序。另外返回的下标是基于1。
思路

由于有序，维护一左一右两个指针，所指数的和过小，则左指针右移一格；过大，右指针左移一格；等于则返回结果。
复杂度

T(N)=O(N),M(N)=O(1)T(N)=O(N),M(N)=O(1)T(N)=O(N),M(N)=O(1)
结果

(0ms, 100.0%, 36.9 MB, 100.0%)
源码

class Solution {

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

        // twoSumWithSortedArr

        // 已经确保了答案存在

        int l = 0;

        int r = nums.length-1;

        int t;

        while (true) {

            t = nums[l]+nums[r];

            if (t < target)

                ++l;

            else if (t > target)

                --r;

            else

                return new int[] {l+1,r+1};

        }

    }

}

3Sum

题意

给定一个数组，从中选三个元素a,b,c.使得a+b+c=0.给出所有的可能的三元组(unique triplets)的集合。
思路1

原数组分为负数和非负数两个数组。则答案只有这些可能：

3个0的特殊判断。

情况1枚举负数，转换为非负数数组中的two Sum问题。

情况2同理。

思路2

先排序，直接枚举一个数。转化为Two Sum II问题。
复杂度

思路1T(N)=O(N2),M(N)=O(N)T(N)=O(N^2),M(N)=O(N)T(N)=O(N2),M(N)=O(N)

思路2T(N)=O(N2),M(N)=O(1)T(N)=O(N^2),M(N)=O(1)T(N)=O(N2),M(N)=O(1)

且考虑到思路2变成复杂度更低。毫无疑问选思路2.
结果

(37ms, 99.61%, 48.5MB, 100.00%)
源码

class Solution {

    public List<List<Integer>> threeSum(int[] nums) {

        int target = 0;

        List<List<Integer>> ans = new ArrayList<List<Integer>>();

        Arrays.sort(nums);

        int len = nums.length;

        for (int i = 0; i+3 <= len; ++i) {

            if (nums[i]*3 > target)

                break;

            if (i > 0 && nums[i] == nums[i-1])

                continue;

            int part_target = target-nums[i];

            int range[] = {i+1,len-1};

            while (range[0] < range[1]) {

                twoSum(nums,part_target,range);

                if (range[0] >= range[1])

                    break;

                // found a ans

                List<Integer> l = new ArrayList<Integer>();

                l.add(nums[i]);

                l.add(nums[range[0]]);

                l.add(nums[range[1]]);

                ans.add(l);

                // move

                do{

                    ++range[0];

                }while(range[0] < range[1] && nums[range[0]] == nums[range[0]-1]);

            }

        }

        return ans;

    }

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

        int t;

        while (range[0] < range[1]) {

            t = nums[range[0]]+nums[range[1]];

            if (t < target)

                ++range[0];

            else if (t > target)

                --range[1];

            else

                return;

        }

    }

}

4Sum

题意

类似于3Sum.只是变成4个数了。并且目标和不是固定的0，而是通过输入参数指定。
思路

直接循环枚举，注意控制条件以免重复。

其实应该写搜索的，但是枚举更加无脑暴力，就直接敲了。
复杂度

T(N)=O(N3),M(N)=O(1)T(N)=O(N^3),M(N)=O(1)T(N)=O(N3),M(N)=O(1)
结果

(19ms, 89.95%, 40MB, 100.00%)
源码

class Solution {

    public List<List<Integer>> fourSum(int[] nums, int target) {

        List<List<Integer>> ans = new ArrayList<List<Integer>>();

        Arrays.sort(nums);

        int len = nums.length;

        for (int i = 0; i+4 <= len; ++i) {

            if (nums[i]*4 > target)

                break;

            if (i > 0 && nums[i] == nums[i-1])

                continue;

            for (int j = i+1; j+3 <= len; ++j) {

                if (nums[i]+nums[j]*3 > target)

                    break;

                if (j > i+1 && nums[j] == nums[j-1])

                    continue; // 前一个数并非是a,[j]和前一个数相同,则没必要用[j]再当b

                int part_target = target-nums[i]-nums[j];

                int range[] = {j+1,len-1};

                while (range[0] < range[1]) {

                    twoSum(nums,part_target,range);

                    if (range[0] >= range[1])

                        break;

                    // found a ans

                    List<Integer> l = new ArrayList<Integer>();

                    l.add(nums[i]);

                    l.add(nums[j]);

                    l.add(nums[range[0]]);

                    l.add(nums[range[1]]);

                    ans.add(l);

                    // move

                    do{

                        ++range[0];

                    }while(range[0] < range[1] && nums[range[0]] == nums[range[0]-1]);

                }

            }

        }

        return ans;

    }

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

        int t;

        while (range[0] < range[1]) {

            t = nums[range[0]]+nums[range[1]];

            if (t < target)

                ++range[0];

            else if (t > target)

                --range[1];

            else

                return;

        }

    }

}