Share my clean 2sum-style Java code with brief explanation


  • 3
    M
    /*
        -- 先排序 [-2,-1,0,0,1,2]
        -- 在[0...len-3]中枚举前两个数pair, 注意重复的pair就不要选了, 虽然后面两个数的可选域会不一样.
            -2,-1 -- [0,0,1,2]
            -2,0 -- [0,1,2]
            -2,0 -- [1,2]
            -1,0 -- [0,1,2]
            -1,0 -- [1,2]
            0,0 -- [1,2]
            例如-2,0 -- [0,1,2] 和 -2,0 -- [1,2], 在考虑[0,1,2]的时候必定已考虑过[1,2]
        -- 剩下的按2sum做
    */
    public class Solution {
        public List<List<Integer>> fourSum(int[] nums, int target) {
            List<List<Integer>> ans = new ArrayList<>();
            Arrays.sort(nums);
            for (int i = 0; i < nums.length - 3; ) {  // (i, j) enumerate each pair in [0...length-3]
                for (int j = i + 1; j < nums.length - 2; ) {
                    for (int m = j + 1, n = nums.length - 1; m < n;) {  // (m, n) is normal 2sum pair
                        int sum = nums[i] + nums[j] + nums[m] + nums[n];
                        if (sum < target) { ++m; }
                        else if (sum > target) { --n; }
                        else {  // sum == target
                            ans.add(new ArrayList<Integer>(Arrays.asList(nums[i], nums[j], nums[m], nums[n])));
                            int k = m + 1;
                            while (k < n && nums[k] == nums[m]) { ++k; }
                            m = k;
                        }
                    }
                    int k = j + 1;
                    while (k < nums.length - 2 && nums[k] == nums[j]) { ++k; }
                    j = k;
                }
                int k = i + 1;
                while (k < nums.length - 3 && nums[k] == nums[i]) { ++k; }
                i = k;
            }
            return ans;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.