18 - 4Sum

 

• class Solution {
      public List<List<Integer>> fourSum(int[] nums, int target) {
          int n = nums.length;
          List<List<Integer>> ans = new ArrayList<>();
          if (n < 4) {
              return ans;
          }
          Arrays.sort(nums);
          for (int i = 0; i < n - 3; ++i) {
              if (i > 0 && nums[i] == nums[i - 1]) {
                  continue;
              }
              for (int j = i + 1; j < n - 2; ++j) {
                  if (j > i + 1 && nums[j] == nums[j - 1]) {
                      continue;
                  }
                  int k = j + 1, l = n - 1;
                  while (k < l) {
                      long x = (long) nums[i] + nums[j] + nums[k] + nums[l];
                      if (x < target) {
                          ++k;
                      } else if (x > target) {
                          --l;
                      } else {
                          ans.add(List.of(nums[i], nums[j], nums[k++], nums[l--]));
                          while (k < l && nums[k] == nums[k - 1]) {
                              ++k;
                          }
                          while (k < l && nums[l] == nums[l + 1]) {
                              --l;
                          }
                      }
                  }
              }
          }
          return ans;
      }
  }
  
  
  //
  
  // general solution, k-sum
  // https://leetcode.com/problems/4sum/solution/
  // below kSum() divide-and-conquer idea is good, but not passing Online-Judge
  class Solution {
  
  	public List<List<Integer>> fourSum(int[] nums, int target) {
  		Arrays.sort(nums);
  		return kSum(nums, target, 0, 4);
  	}
  
  	public List<List<Integer>> kSum(int[] nums, int target, int start, int k) {
  		List<List<Integer>> res = new ArrayList<>();
  		if (start == nums.length || nums[start] * k > target || target > nums[nums.length - 1] * k)
  			return res;
  		if (k == 2)
  			return twoSum(nums, target, start);
  		for (int i = start; i < nums.length; ++i)
  			if (i == start || nums[i - 1] != nums[i]) // 'i == start' is key, since it could be in a following recurion of [1,1,1] where start is 3rd '1'
  				for (List<Integer> set : kSum(nums, target - nums[i], i + 1, k - 1)) {
  					res.add(new ArrayList<>(Arrays.asList(nums[i])));
  					res.get(res.size() - 1).addAll(set);
  				}
  		return res;
  	}
  
  	public List<List<Integer>> twoSum(int[] nums, int target, int start) {
  		List<List<Integer>> res = new ArrayList<>();
  		int lo = start, hi = nums.length - 1;
  		while (lo < hi) {
  			int sum = nums[lo] + nums[hi];
  			if (sum < target || (lo > start && nums[lo] == nums[lo - 1]))
  				++lo;
  			else if (sum > target || (hi < nums.length - 1 && nums[hi] == nums[hi + 1]))
  				--hi;
  			else
  				res.add(Arrays.asList(nums[lo++], nums[hi--]));
  		}
  		return res;
  	}
  }
  
  
  public class Four_Sum {
  
      public static void main(String[] args) {
          Four_Sum out = new Four_Sum();
          Solution s = out.new Solution();
  //		SolutionForLoop s= out.new SolutionForLoop();
  
          List<List<Integer>> result = s.fourSum(new int[]{1, 0, -1, 0, -2, 2}, 0);
  
          for (List<Integer> each : result) {
              String one = "";
  
              for (int e : each) {
                  one = one + " " + e;
              }
  
              System.out.println(one);
          }
      }
  
      // time: O(NlogN)
      // space: O(1)
      public class Solution {
          public List<List<Integer>> fourSum(int[] nums, int target) {
  
              List<List<Integer>> list = new ArrayList<>();
  
              if (nums.length < 4) {
                  return list;
              }
  
              Arrays.sort(nums);
  
              // improved based on 3-sum
              int layer4 = 0;
              while (layer4 < nums.length) {
  
                  // @note: below is causing me trouble when convert for to while
                  // 			in while, here "layer4" is never updated for case like {0,0,0,0}
                  // if(layer4 > 0 && nums[layer4] == nums[layer4 - 1]) continue;
                  if (layer4 > 0 && nums[layer4] == nums[layer4 - 1]) {
                      layer4++;
                  }
  
                  // hold one pointer, other two pointer moving
                  int ancher = layer4 + 1;
                  while (ancher < nums.length) {
  
                      int i = ancher + 1;
                      int j = nums.length - 1;
  
                      while (i < j) {
  
                          int sum = nums[layer4] + nums[ancher] + nums[i] + nums[j];
  
                          if (sum == target) {
  
                              // @note: Arrays.asList()
                              list.add(Arrays.asList(nums[layer4], nums[ancher], nums[i], nums[j]));
  
                              // @note: dont forget move pointers
                              i++;
                              j--;
  
                              // @note: optimization. above i,j is updated already, compare with previous position
                              while (i < j && nums[i] == nums[i - 1]) {
                                  i++;
                              }
                              while (j > i && nums[j] == nums[j + 1]) {
                                  j--;
                              }
  
                          } else if (sum < target) {
                              i++;
  
                              // @note: same here, possibly updated already, note i-1 or i+1
                              while (i < j && nums[i] == nums[i - 1]) {
                                  i++;
                              }
  
                          } else {
                              j--;
  
                              // @note: same here, possibly updated already, note i-1 or i+1
                              while (j > i && j + 1 < nums.length && nums[j] == nums[j + 1]) {
                                  j--;
                              }
  
                          }
                      }
  
                      ancher++;
  
                      // optimize for 2nd pointer
                      while (ancher > layer4 && ancher < nums.length && nums[ancher] == nums[ancher - 1]) {
                          ancher++;
                      }
  
                  }
  
                  layer4++;
  
                  // optimize for 2nd pointer
                  while (layer4 < nums.length && nums[layer4] == nums[layer4 - 1]) {
                      layer4++;
                  }
              }
  
              return list;
          }
      }
  }
  

C++

• class Solution {
  public:
      vector<vector<int>> fourSum(vector<int>& nums, int target) {
          int n = nums.size();
          vector<vector<int>> ans;
          if (n < 4) {
              return ans;
          }
          sort(nums.begin(), nums.end());
          for (int i = 0; i < n - 3; ++i) {
              if (i && nums[i] == nums[i - 1]) {
                  continue;
              }
              for (int j = i + 1; j < n - 2; ++j) {
                  if (j > i + 1 && nums[j] == nums[j - 1]) {
                      continue;
                  }
                  int k = j + 1, l = n - 1;
                  while (k < l) {
                      long long x = (long long) nums[i] + nums[j] + nums[k] + nums[l];
                      if (x < target) {
                          ++k;
                      } else if (x > target) {
                          --l;
                      } else {
                          ans.push_back({nums[i], nums[j], nums[k++], nums[l--]});
                          while (k < l && nums[k] == nums[k - 1]) {
                              ++k;
                          }
                          while (k < l && nums[l] == nums[l + 1]) {
                              --l;
                          }
                      }
                  }
              }
          }
          return ans;
      }
  };