SHARE
TWEET

3Sum = 0 | Time: O(n^2) | Space: O(1)

a guest Jul 22nd, 2019 57 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*  Leetcode problem: https://leetcode.com/problems/3sum/
  2.     Used solution as reference: https://leetcode.com/problems/3sum/discuss/7399/Easiest-Java-Solution
  3. */
  4.  
  5. import java.util.ArrayList;
  6. import java.util.Arrays;
  7. import java.util.List;
  8.  
  9. public class ThreeSum {
  10.    
  11.     public static List<List<Integer>> threeSum(int[] nums) {
  12.         List<List<Integer>> results = new ArrayList<>();
  13.         Arrays.sort(nums);
  14.  
  15.         for (int i = 0; i < nums.length - 2; i++) {
  16.             // skip same result
  17.             if (i > 0 && nums[i] == nums[i - 1]) {              
  18.                 continue;
  19.             }
  20.  
  21.             int left = i + 1;
  22.             int right = nums.length - 1;
  23.             int target = -nums[i];
  24.             while(left < right) {
  25.                 if (nums[left] + nums[right] == target) {
  26.                     results.add(Arrays.asList(nums[i], nums[left], nums[right]));
  27.                     left++;
  28.                     right--;
  29.                     while (left < right && nums[left] == nums [left -1]) left++; // skip the same result
  30.                     while (left < right && nums[right] == nums [right + 1]) right--; // skip the same result
  31.                 } else if (nums[left] + nums [right] < target) {
  32.                     left++;
  33.                 } else {
  34.                     right--;
  35.                 }
  36.             }
  37.         }
  38.         return results;
  39.     }
  40.  
  41.     public static void main(String arg[]) {
  42.         int[]testInput = {-1, 0, 1, 2, -1, -4};
  43.         List<List<Integer>> result = threeSum(testInput);
  44.         System.out.println("Results are: ");
  45.         for (List<Integer> list : result) {
  46.             System.out.println(list);
  47.         }
  48.        
  49.     }
  50. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top