Fork me on GitHub

Leetcode-Thirteen-arraySum

发表于 | 分类于 | 阅读次数:

Array Sum

Two Sum

Description

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].

Analysis

给出一个数组 arr[1…n] 和一个数字 k，求数组中和为 k 的两个元素的下标。很通常的想法，我们可以通过两层循环，遍历数组中可以组合的所有数对，查询所有的情况。由于题目保证一定有解，所以，必定可以找到答案。这个算法的复杂度为 $O(n^2)$

AC Picture

AC

Code

1
2
3
4
5
6
7
8
9
10
vector<int> twoSum(vector<int>& nums, int target) {
  int size = nums.size();
  for (int i = 0; i < size-1; ++i) {
    for (int j = i+1; j < size; ++j) {
      if (nums[i] + nums[j] == target) {
        return vector<int>{i, j};
      }
    }
  }
}

Further

算法运行时间太长了，比最优情况要慢一倍。我们来想办法优化算法：
题目的数组是无序的，但如果数组有序，我们可以采用双指针的方法。初始，头指针指向数组最小的元素，尾指针指向数组最大的元素。

接下来，我们计算两个指针所指元素的和 sum，并且与目标 k 进行比较。如果 sum 比 k 小，那么由于尾指针所指元素已经是最大元素，则只能移动头指针，来增大 sum；如果 sum 比 k 大，那么由于头指针指向最小元素，所以，移动尾指针，减小 sum。如果 sum 等于 k，那么找到目标。而且题目保证唯一解，所以，对于没有匹配的元素，则必定不是解。那么，双指针的算法复杂度是多少呢？由于每个元素只访问一次，所以算法复杂度为 $O(n)$。
但是我们原始数组是无序的，所以需要先排序。排序的复杂度我们可以使用快排，那么排序复杂度为 $O(nlogn)$。所以最终的算法复杂度为 $O(nlogn)$。

由于我们需要输出原始下标，所以我们还需要存储原始的下标，避免排序后无法找回原始下标。这里采用一个pair数组存储，也可以使用map。

AC

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
vector<int> twoSum(vector<int>& nums, int target) {
  vector<pair<int, int> > temp;
  int size = nums.size();
  for (int i = 0; i < size; ++i) {    
    temp.push_back({nums[i], i});
  }
  std:sort(temp.begin(), temp.end());
  int i = 0, j = size - 1;
  while (i < j) {
    if (temp[i].first + temp[j].first < target) ++i;
    else if (temp[i].first + temp[j].first > target) --j;
    else if (temp[i].first + temp[j].first == target)    
      return vector<int>{temp[i].second, temp[j].second};
  }
  return vector<int>{0,0};
}

Three Sum

Description

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

Example

Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:[[-1, 0, 1],[-1, -1, 2]]

Analysis

最通常的算法，就是 $O(n^3)$ 的算法，直接三次循环。由于我们先做了 Two Sum，可以转换下想法，利用前面的算法，降低我们的算法复杂度。
首先这里只要输出数组元素，所以排序是没有关系的，算法复杂度 $O(nlogn)$。接着我们对于每一个元素 $a_i$，查找在其之后的元素中，是否存在和为 $-a_i$ 的元素对，存在即为解。这个过程使用 Two Sum 的双指针算法。那么每个元素，我们最多访问两遍，所以这里的查找解的算法复杂度为 $O(n^2)$。

NOTE: 由于数组中会有重复数组，所以，我们每找到一个解，我们需要调整双指针，直到找到非相同元素，否则，解集中将出现重复解。

AC Picture

AC

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
vector<vector<int>> threeSum(vector<int>& nums) {
  vector<vector<int> > res;
  std:sort(nums.begin(), nums.end());
  int size = nums.size(), target = 0;
  int j = 0, k = 0;
  for (int i = 0; i < size - 2; ++i) {
    target = -nums[i];
    j = i + 1;
    k = size - 1;
    while (j < k) {
      if (nums[j] + nums[k] < target) ++j;
      else if (nums[j] + nums[k] > target) --k;
      else {
        vector<int> triple{nums[i], nums[j], nums[k]};
        res.push_back(triple);

        while (j < k && nums[j] == triple[1])   ++j;
        while (j < k && nums[k] == triple[2])   --k;
     }
    }
    while ((i < size - 2) && nums[i] == nums[i+1])  ++i;
  }
  return res;
}