Clean O(n^3) code use 4 pointers and 2Sum.


  • 0
    K
    public class Solution {
        public List<List<Integer>> fourSum(int[] nums, int target) {
            List<List<Integer>> resultSet = new ArrayList<>();
            if(nums == null || nums.length < 4)
                return resultSet;
            Arrays.sort(nums);
            int start = 0, end = nums.length -1, first_ptr , last_ptr;
            while(start + 3 <= end) {
                first_ptr = start;
                last_ptr = end;
                while (first_ptr + 3 <= last_ptr) {
                    int two_sum = target - nums[first_ptr] - nums[last_ptr];
                    int inner_first_ptr = first_ptr + 1, inner_second_ptr = last_ptr - 1;
                    while (inner_first_ptr < inner_second_ptr) {
                        int cur_sum = nums[inner_first_ptr] + nums[inner_second_ptr];
                        if (cur_sum < two_sum) {
                            inner_first_ptr++;
                        } else if (cur_sum > two_sum) {
                            inner_second_ptr--;
                        } else {
                            resultSet.add(Arrays.asList(nums[first_ptr], nums[inner_first_ptr], nums[inner_second_ptr], nums[last_ptr]));
                            while (inner_first_ptr < last_ptr && nums[inner_first_ptr + 1] == nums[inner_first_ptr])
                                inner_first_ptr++;
                            while (inner_second_ptr > first_ptr && nums[inner_second_ptr - 1] == nums[inner_second_ptr])
                                inner_second_ptr--;
                            inner_first_ptr++;
                            inner_second_ptr--;
                        }
                    }
                    while (first_ptr < nums.length - 4 && nums[first_ptr + 1] == nums[first_ptr])
                        first_ptr++;
                    first_ptr++;
                }
                while (end > 3 && nums[end - 1] == nums[end])
                    end--;
                end--;
            }
            return resultSet;
        }
    }
    

Log in to reply
 

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