Why is the time limit exceeded for my solution


  • 0
    Z

    I think the following code's time complexity is also O(n^2) which should be accepted as the answer, but instead of being accepted, it exceeded the time limit. Please explain the reason why it exceeded the time limit to me.

    public static List<List<Integer>> threeSum(int[] nums) {
    		if (nums == null) {
    			return new ArrayList<List<Integer>>();
    		}
    		List<List<Integer>> result = new ArrayList<List<Integer>>();
    		Arrays.sort(nums);
    		for (int i = 0; i < nums.length; i++) {
    			int curr = nums[i];
    
    			int minIndex = (i == 0) ? i + 1 : i - 1;
    			int maxIndex = (i == nums.length - 1) ? i - 1 : nums.length - 1;
    
    			while (minIndex < maxIndex) {
    				if (curr + nums[minIndex] + nums[maxIndex] == 0) {
    					if (i < minIndex) {
    						result.add(Arrays.asList(new Integer[] { i, minIndex,
    								maxIndex }));
    					} else if (i > maxIndex) {
    						result.add(Arrays.asList(new Integer[] { minIndex,
    								maxIndex, i }));
    					} else {
    						result.add(Arrays.asList(new Integer[] { minIndex, i,
    								maxIndex }));
    					}
    					maxIndex--;
    					if (maxIndex == i) {
    						maxIndex--;
    					}
    					minIndex++;
    					if (minIndex == i) {
    						minIndex++;
    					}
    				} else if (curr + nums[minIndex] + nums[maxIndex] > 0) {
    					maxIndex--;
    					if (maxIndex == i) {
    						maxIndex--;
    					}
    				} else {
    					minIndex++;
    					if (minIndex == i) {
    						minIndex++;
    					}
    				}
    
    			}
    		}
    		return result;
    	}

Log in to reply
 

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