leetcode 之Sum系列（七）

第一题是Two Sum

同样是用哈希表来做，需要注意的是在查打gap是要排除本身。比如target为4，有一个值为2，gap同样为2。

 vector<int> twoSum(vector<int> &num, int target)
      {
          unordered_map<int, int> mapping;
          vector<int> result;
          for (int i = 0; i < num.size(); i++)
              mapping[num[i]] = i;

          for (int i = 0; i < num.size(); i++)
          {
              int gap = target - num[i];
              //第二个判断条件更准确的是mapping[gap]！=i，防止选到自身
              if (mapping.find(gap) != mapping.end()&&mapping[gap]>i)
              {
                  result.push_back(i + 1);
                  result.push_back(mapping[gap] + 1);
                  break;
              }
          }

          return result;
      }

View Code

接下来是3Sum

这题需要注意的是如何去重

vector<vector<int>> threeSum(vector<int> &num)
      {
          vector<vector<int>>result;
          if (num.size() < 3)return;

          sort(num.begin(), num.end());
          auto last = num.end();//最后一个元素的下一个
          for (auto i = num.begin(); i < last - 2; i++)
          {
              auto j = i + 1;
              //注意重复的判断
              if (i>num.begin() && *(i) == *(i - 1))continue;
              auto k = last - 1;
              while (j < k)
              {
                  if (*(i)+*(j)+*(k) < 0)
                  {
                      j++;
                      while (*(j) == *(j - 1) && j < k)j++;
                  }
                  else if (*(i)+*(j)+*(k) > 0)
                  {
                      k--;
                      while (*(k) == *(k +1) && k>j)k--;
                  }
                  else
                  {
                      result.push_back({*(i),*(j),*(k)});
                      j++;
                      k--;
                      while (*(j) == *(j - 1) && j < k)j++;
                      while (*(k) == *(k + 1) && k>j)k--;
                  }
              }
          }
          return result;
      }

View Code

接下来是3Sum Closet，和上题思路一样，代码中我没有去重，实际上应该要去重。

int threeSumCloset(vector<int>&num, int target)
      {
          int result = 0;
          int min_gap = INT_MIN;

          sort(num.begin(), num.end());
          for (auto a = num.begin(); a != prev(num.end(), 2); a++)
          {
              auto b = next(a);
              auto c = prev(num.end());

              while (b < c)
              {
                  int sum = *(a)+*(b)+*(c);
                  int gap = abs(sum - target);

                  if (gap < min_gap)
                  {
                      result = sum;
                      min_gap = gap;
                  }

                  if (sum < target)b++;
                  else c--;
              }
          }

          return result;
      }

View Code

4Sum采用相同的思路，不过它的去重放在了最后。需要注意去重的方法，unique并非真的去掉了重复元素，而是将重复元素放在了最后，unique返回的也是

重复元素开始时的迭代器。

vector<vector<int>> fourSum(vector<int>& num, int target) {
vector<vector<int>> result;
if (num.size() < 4) return result;
sort(num.begin(), num.end());
auto last = num.end();
for (auto a = num.begin(); a < prev(last, 3); ++a) {
for (auto b = next(a); b < prev(last, 2); ++b) {
auto c = next(b);
auto d = prev(last);
while (c < d) {
if (*a + *b + *c + *d < target) {
++c;} else if (*a + *b + *c + *d > target) {
--d;
} else {
result.push_back({ *a, *b, *c, *d });
++c;
--d;
}
}
}
}
sort(result.begin(), result.end());
result.erase(unique(result.begin(), result.end()), result.end());
return result;
}

View Code