My Java Accept Code In Consideration Of With Some Tricks,8ms!!


  • 0
    Z
    public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
    	int length = nums.length;
    	if (length < 3) {
    		return result;
    	}
    	Arrays.sort(nums);
    	for (int i = 0; i < length - 2; i++) {
    		if (nums[i] > 0) {
    			return result;
    		}
    		if (i == 0 || nums[i] != nums[i - 1]) {
    			int target = -nums[i];
    			int low = i + 1, high = length - 1;
    			while (low < high) {
    				if (nums[high] < 0 || nums[low] > target) {
    					break;
    				}
    				if (nums[low] + nums[high] == target) {
    					result.add(Arrays.asList(nums[i], nums[low], nums[high]));
    					while(++low<high && nums[low] == nums[low-1]);
    					while(low<--high && nums[high] == nums[high+1]);
    				} else if (nums[low] + nums[high] < target) {
    					while(++low<high && nums[low] == nums[low-1]);
    				} else {
    					while(low<--high && nums[high] == nums[high+1]);
    				}
    			}
    		}
    	}
    	return result;
    }
    

    }


  • 0
    Z

    1.if nums[i] is bigger than zero ,because nums[low] and nums[high] also greater than nums[i],so they can't get sum of zero,so we stop.

    2.if nums[low] is bigger than target,then skip the compare of this nums[i].because nums[high] is bigger than nums[low],but low is still growing.so we can't get the sum equal to target

    3.if nums[high] is less than zero,then skip the compare of this nums[i].nums[high] is bigger than nums[low],so nums[low] is also less than zero.but target is bigger than zero.


  • 0
    A

    Nice one. Since we don't need to search anything from "result", I suggest to use LinkedList instead, which is faster for adding nodes.


Log in to reply
 

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