請我很好奇是否有更好的方法可以解決Leetcode ThreeSum 問題。
我想出了使用二分搜索的這段代碼
// Time Complexity: O(nlogn) O(nlogn) == O(nlogn)
// Extra Space Complexity: O(1)
public static List<List<Integer>> threeSumOptimalSolution(int[] nums) {
int n = nums.length;
if (n < 3)
return Collections.emptyList();
Arrays.sort(nums);
List<List<Integer>> result = new ArrayList<>();
int left;
int right;
int mid;
int threeSum;
for (int firstValue = 0; firstValue < n - 2; firstValue ) {
if (firstValue == 0 || nums[firstValue] != nums[firstValue - 1]) {
left = firstValue 1;
right = n - 1;
while (left < right) {
mid = left (right - left) / 2;
threeSum = nums[firstValue] nums[left] nums[right];
if (threeSum < 0) {
if (nums[mid] nums[right] nums[firstValue] < 0)
left = mid 1;
else
left ;
} else if (threeSum > 0) {
if (nums[mid] nums[left] nums[firstValue] > 0)
right = mid - 1;
else
right--;
} else {
result.add(List.of(nums[firstValue], nums[left], nums[right]));
left ;
while (nums[left] == nums[left - 1] && left < right)
left ;
while (nums[right] == nums[right - 1] && left < right)
right--;
}
}
}
}
return result;
}
我將不勝感激個人/個人的廣泛審查。
uj5u.com熱心網友回復：
我知道的 ThreeNums 問題的最佳時間復雜度是 O(n^2) 而且我認為你想使用兩個指標來完成這個問題。在您的答案中，二分搜索部分是錯誤的，我不知道您在做什么。正確的方法是在外面遍歷串列，在里面使用兩個指標。例如
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
Arrays.sort(nums);
for(int i = 0; i < nums.length; i ) {
if(nums[i] > 0) break;
if(i > 0 && nums[i] == nums[i-1]) continue;
int left = i 1;
int right = nums.length-1;
while(left < right) {
int sum = nums[i] nums[left] nums[right];
if(sum == 0) {
List<Integer> temp = new ArrayList<>();
temp.add(nums[i]);
temp.add(nums[left]);
temp.add(nums[right]);
res.add(temp);
while(right > left && nums[right] == nums[right-1]) right--;
while(right > left && nums[left] == nums[left 1]) left ;
right--;
left ;
} else if(sum > 0) {
right--;
} else {
left ;
}
}
}
return res;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/498198.html