ampersands ampersands - 1 month ago 9
Java Question

time limit exceeded in a nested for-while loop

Could someone help me understand where this time limited exceeding comes from? The context is that in this threeSum method, given an array, I'm trying to record all possible combinations of three numbers that add up to 0. The original question comes from : https://leetcode.com/problems/3sum/

public class Solution {
public List<List<Integer>> threeSum(int[] nums) {

List<List<Integer>> retList = new ArrayList<List<Integer>>();

Arrays.sort(nums); // O(nlogn)

for (int i=0; i<nums.length-1; i++){
int pleft;
int pright;
if (i!=0){
pleft = i-1;
while((nums[pleft]==nums[i]) && (pleft-1 >=0)){
pleft--;
}
} else {
pleft = i;
}
if (i!=nums.length-2){
pright = i+1;
while((nums[pright]==nums[i]) && (pright+1 < nums.length-1)){
pright++;
}
} else {
pright = i;
}
int sum;
while (true){
sum = nums[pleft]+nums[pright]+nums[i];
if (sum==0){
List<Integer> temp = new ArrayList<Integer>();
temp.add(nums[pleft]);
temp.add(nums[pright]);
temp.add(nums[i]);
retList.add(temp);
if (pleft-1>=0) pleft--;
if (pright+1<nums.length-1) pright++;
} else if (sum>0){
if (pleft-1>=0) pleft--;
} else { // less than zero
if (pright+1<nums.length-1) pright++;
}

}
}


return retList;
}


}

Answer

You're not breaking out of your while(true) loop. That code will just run forever and you won't return a value. You need to add a break or change the while (true) to while (condition)