Easy to understand Java solution using nSum


  • 4
    A
    public class Solution {
        public List<List<Integer>> fourSum(int[] nums, int target) {
            Arrays.sort(nums);
            return nSum(nums, 4, 0, target);
        }
        
        public List<List<Integer>> nSum(int[] nums, int n, int idx, int target) {
            if (n == 2) return twoSum(nums, idx, target);
            List<List<Integer>> result = new ArrayList<List<Integer>>();
            for (int i = idx; i <= nums.length - n; i++) {
                List<List<Integer>> temp = nSum(nums, n - 1, i + 1, target - nums[i]);
                for (List<Integer> l : temp) {
                    l.add(0, nums[i]);
                }
                result.addAll(temp);
                int t = nums[i];
                while (i <= nums.length - n && nums[i] == t) {
                    i++;
                }
                i--;
            }
            return result;
        }
        
        public List<List<Integer>> twoSum(int[] nums, int idx, int target) {
            List<List<Integer>> result = new ArrayList<List<Integer>>();
            int ptr1 = idx, ptr2 = nums.length - 1;
            while (ptr1 < ptr2) {
                if (nums[ptr1] + nums[ptr2] == target) {
                    List<Integer> temp = new ArrayList<Integer>();
                    temp.add(nums[ptr1]);
                    temp.add(nums[ptr2]);
                    result.add(temp);
                    int t = nums[ptr1];
                    while (ptr1 < ptr2 && nums[ptr1] == t) {
                        ptr1++;
                    }
                } else if (nums[ptr1] + nums[ptr2] < target) {
                    ptr1++;
                } else {
                    ptr2--;
                }
            }
            return result;
        }
    }

Log in to reply
 

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