3sum on LeetCode OJ# JobHunting - 待字闺中
Z*A
1 楼
写了3sum的solution，但是没通过OJ large judge，Run Status: Time Limit
Exceeded，请分析一下原因。
下面是code：
public ArrayList> threeSum(int[] num) {
// Start typing your Java solution below
// DO NOT write main() function
if (num.length < 3)
return new ArrayList>();
Arrays.sort(num);
ArrayList> res = new ArrayList
>();
for (int i=0; i < num.length; i++)
{
int target = 0 - num[i];
int low = i+1;
int high = num.length - 1;
while (low < high)
{
int twosum = num[low] + num[high];
if (twosum < target)
low++;
else if (twosum > target)
high--;
else
{
ArrayList triplet = new ArrayList();
triplet.add(num[i]);
triplet.add(num[low]);
triplet.add(num[high]);
if (!res.contains(triplet))
res.add(triplet);
low++;
high--;
}
}
}
return res;
}
Exceeded，请分析一下原因。
下面是code：
public ArrayList
// Start typing your Java solution below
// DO NOT write main() function
if (num.length < 3)
return new ArrayList
Arrays.sort(num);
ArrayList
>();
for (int i=0; i < num.length; i++)
{
int target = 0 - num[i];
int low = i+1;
int high = num.length - 1;
while (low < high)
{
int twosum = num[low] + num[high];
if (twosum < target)
low++;
else if (twosum > target)
high--;
else
{
ArrayList
triplet.add(num[i]);
triplet.add(num[low]);
triplet.add(num[high]);
if (!res.contains(triplet))
res.add(triplet);
low++;
high--;
}
}
}
return res;
}
