Java solution using sorting and binary search


  • 0
    M
    private static List<List<Integer>> threeSum(int[] nums) {
    		List<List<Integer>> pairs = new ArrayList<List<Integer>>();
    		Arrays.sort(nums);
    
    		for (int i = 0; i < nums.length - 2 && nums[i] <= 0; i++) {
    			if (i != 0 && nums[i] == nums[i - 1]) {
    				continue;
    			}
    			for (int j = i + 1; j < nums.length - 1; j++) {
    				if (j == i + 1 || (j > i + 1 && nums[j] != nums[j - 1])) {
    					if (-(nums[i] + nums[j]) >= nums[j]) {
    						int indexOfRequired = Arrays.binarySearch(nums, j + 1, nums.length, -(nums[i] + nums[j]));
    						if (indexOfRequired >= 0) {
    							pairs.add(Arrays.asList(new Integer[] { nums[i], nums[j], nums[indexOfRequired] }));
    						}
    					}
    				}
    
    			}
    		}
    
    		return pairs;
    	}
    

Log in to reply
 

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