wordpress制作功能型网站,上海网站备案在哪里查询,安徽网站设计方案,上海网站建设领导品牌传送门#xff1a;三数之和
思路
为了去重#xff0c;需要先排序。
排序之后#xff0c;显然每一个 n u m s [ i ] nums[i] nums[i] 就可以作为三数之中的第一个数。
因此#xff0c;对于每一个 i i i#xff0c;第二、三个数只能在 [ i 1 , n ] [i 1, n] [i1,n]…传送门三数之和
思路
为了去重需要先排序。
排序之后显然每一个 n u m s [ i ] nums[i] nums[i] 就可以作为三数之中的第一个数。
因此对于每一个 i i i第二、三个数只能在 [ i 1 , n ] [i 1, n] [i1,n] 之间取得。
这时候如果使用 map 去维护每个 nums 对应的所有下标例如std::map int, std::vectorint mp;实际上还是会超时。因为即使确定了第一、二个数当查找第三个数时哪怕用二分都还要再乘上一个 l o g n logn logn 的复杂度。
但这也同时提醒我们如果确定了第二、三个数那就可以判断出 n u m s [ 2 ] n u m s [ 3 ] nums[2] nums[3] nums[2]nums[3] 是大于还是小于 − n u m s [ 1 ] - nums[1] −nums[1]这就意味着我们可以通过移动 2、3 指针的方式来找到 n u m s [ 2 ] n u m s [ 3 ] − n u m s [ 1 ] nums[2] nums[3] - nums[1] nums[2]nums[3]−nums[1] 的情况。
因此这道题可以用双指针的方式来做还是有点难想的。 还需要额外注意 [… , a , a , …] 和 [ … , a , b , b , … ] 这两种特殊情况。 代码
class Solution {
public:vectorvectorint threeSum(vectorint nums) {std::sort(nums.begin(), nums.end());std::vectorstd::vectorint result;for (int i 0; i nums.size(); i) {int sum -nums[i];// 防止 a aif (i 1 nums[i] nums[i - 1]) continue;int r nums.size() - 1; for (int l i 1; l nums.size(); l) {// 防止 a b bif (l i 1 nums[l] nums[l - 1]) continue;while (r l nums[l] nums[r] sum) r--;if (l r) break;if (nums[l] nums[r] sum) {result.push_back({nums[i], nums[l], nums[r]});}}} return result;}
};
