【剑指offer】——和为s的序列

文章目录

1、和为s的两个数字2、和为s的连续正数序列

1、和为s的两个数字

1、题目要求 输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。

示例1： 输入：nums = [2,7,11,15], target = 9 输出：[2,7] 或者 [7,2]

示例2： 输入：nums = [10,26,30,31,47,60], target = 40 输出：[10,30] 或者 [30,10]

限制： 1 <= nums.length <= 10^5 1 <= nums[i] <= 10^6

2、题目分析 方法一：两层for循环来挨个比较 因为这种方法的时间复杂度太高了，达到了O(n^2)。太过于繁琐，我们在此就不多加讨论。代码实现如下：

vector<int> twoSum(vector<int>& arr, int target) { vector<int> res; for (int i = 0; i < arr.size(); i++) { int sum = arr[i]; for (int j = i+1; j < arr.size(); j++) { int temp = sum + arr[j]; if (temp == target) { res.clear(); res.push_back(arr[i]); res.push_back(arr[j]); break; } } } return res; }

方法二:利用二分查找 有了方法一的一个大概思路。我们想要降低其时间复杂度的话，其实就要牢牢抓住数组有序的特点使用二分查找来完成问题的求解。

首先一个for循环，固定住arr[i]。然后另外一个值other=target-arr[i]。然后就是利用二分查找的方式去寻找符合条件的other值。找到就压入数组进行退出。注意！！！这个退出是指的退出程序而不是退出循环。这样的时间复杂度是O（nlogn）

代码实现如下：

vector<int> twoSum1(vector<int>& arr, int target) { int high = arr.size() - 1; vector<int> res; for (int i = 0; i < arr.size(); i++) { int other = target - arr[i]; int index = i; while (index <= high) { int mid = (high - index + 1) / 2 + index; if (arr[mid] == other) { res.push_back(arr[mid]); res.push_back(arr[i]); return res; } else if (arr[mid] > other) { high = mid - 1; } else index = mid + 1; } } return res; }

方法三：双指针的方式 要充分利用数组有序的特点。

定义两个指针head和tail分别指向数组的头部和尾部。并定义sum = arr[head]+arr[tail]当发现sum>target的时候，需要减少sum的值，所以让tail–。head++同理找到了相等的值就依次将arr[head]和arr[tail]压入数组返回即可。注意！！！找到了一定要使用break;时间复杂度是O（n）

代码实现如下：

vector<int> twoSum2(vector<int>& arr, int target) { vector<int> res; if (arr.size() == 0) { return res; } int head = 0; int tail = arr.size() - 1; while (head < tail) { int sum = arr[head] + arr[tail]; if (sum > target) { tail--; } else if(sum < target) { head++; } else { res.push_back(arr[head]); res.push_back(arr[tail]); break; } } return res; } int main() { vector<int> res; res.push_back(16); res.push_back(16); res.push_back(18); res.push_back(24); res.push_back(30); res.push_back(32); vector<int> a = twoSum2(res, 48); for (int i = 0; i < a.size(); i++) { cout << a[i]<<" "; } return 0; }

3、改进——求数组里面和为target的所有组合 前面两种方式的改进在这儿就不再做赘述，主要来讲一讲最后一种双指针解法的改进。 改进的主要的点就在于，当找到了sum=target的情况后

首先将两个数压入vector容器temp里面,让将一维数组temp的数压入二维数组vec当中。但是最后一定要记住将一维数组清空。 temp.clear()。接着low++,high–接着要去寻找剩下序列里面的和为k的数对。所以此时不应该break。

具体代码实现如下：

vector<vector<int>> twoSum4(vector<int> arr, int target) { vector<int> res; vector<vector<int>> vec; //考虑特殊情况 if (arr.size() == 0) { return vec; } sort(arr.begin(), arr.end()); int low = 0; int high = arr.size() - 1; int count = 0; while (low < high) { int sum = arr[low] + arr[high]; if (sum < target) { low++; } else if (sum > target) { high--; } else { res.push_back(arr[low]); res.push_back(arr[high]); vec.push_back(res); res.clear(); low++; high--; } } return vec; } int main() { vector<int> res; int n; cin >> n; for (int i = 0; i < n; i++) { int temp; cin >> temp; res.push_back(temp); } vector<vector<int>> arr = twoSum4(res, 8); for (int j = 0; j < arr.size(); j++) { for (int i = 0; i < arr[i].size(); i++) { cout << arr[j][i] << " "; } cout << endl; } return 0; }

同理，如果再改编一下，求出和为target的数对个数，就在上面代码的基础上做更改，输入一个count值就可。

2、和为s的连续正数序列

1、题目大意 输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。 序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。

示例1： 输入：target = 9 输出：[[2,3,4],[4,5]]

示例2： 输入：target = 15 输出：[[1,2,3,4,5],[4,5,6],[7,8]]

2、题目分析 从题目要求里面我们可以看到，要求我们的返回值得是一个二维数组。所有我们得定义一个二维数组来保存最后返回的结果值。

还是使用两个for循环的暴力方法来求解问题。第一层循环i从1开始，循环的中止条件是i<=(target+1)/2。内层循环从j=i开始进行累加得到sum.。中止条件相同。遇到sum > target的情况就清空一位数组，跳出第二个for循环。

具体的还是以具体的例子来加以说明： 代码实现：

vector<vector<int>> findContinuousSequence(int target) { vector<vector<int>> result; vector<int> temp; for (int i = 1; i <= ((target + 1) / 2); i++) { int sum = 0; for (int j = i ; j <= ((target + 1) / 2); j++) { sum += j; temp.push_back(j); if (sum > target) { temp.clear(); break; } else if(sum == target) { result.push_back(temp); break; } } } return result; } int main() { vector<vector<int>> res; res = findContinuousSequence(9); for (int i = 0; i < res.size(); i++) { for (int j = 0; j < res[i].size(); j++) { cout << res[i][j]<<" "; } cout << endl; } return 0; }

3、改进 数组序列不是从1到target的有序序列，而是用户输入的有序的不连续序列。求和为target的连续序列。 【举个栗子】数组序列为{1,1,2，3,4，7,8，10}，target为7。则输出序列为[[1,1,2,3],[3,4]]。

vector<vector<int>> twoSum5(vector<int> arr, int target) { sort(arr.begin(), arr.end()); vector<int> temp; vector<vector<int>> result; for (int i = 0; i < arr.size(); i++) { int sum = arr[i]; temp.push_back(arr[i]); for (int j = i + 1; j < arr.size(); j++) { sum += arr[j]; temp.push_back(arr[j]); if (sum > target) { temp.clear(); break; } else if(sum == target) { result.push_back(temp); temp.clear(); break; } } } return result; } int main() { vector<int> res; int n; cin >> n; for (int i = 0; i < n; i++) { int temp; cin >> temp; res.push_back(temp); } vector<vector<int>> arr = twoSum5(res, 7); for (int i = 0; i < arr.size(); i++) { for (int j = 0; j < arr[i].size(); j++) { cout << arr[i][j] << " "; } cout << endl; } return 0; }