三数之和
1.问题描述
给定一个包含n个整数的数组nums，判断nums中是否存在三个元素a，b，c，使得a+b+c=0？找出所有和为0且不重复的三元组。
2.输入输出
- 输入：nums=[-1,0,1,2,-1,-4]
- 输出：[[-1,-1,2], [-1,0,1]]
3.算法分析
【排序+双指针】
- 特判，对于数组长度 n，如果数组为null或者数组长度小于3，返回 [][]。
- 对数组进行排序。
- 遍历排序后数组：
- 若 nums[i]>0：因为已经排序好，所以后面不可能有三个数加和等于0，直接返回结果。
对于重复元素：跳过，避免出现重复解- 令左指针 L=i+1，右指针 R=n-1，当 L<R时，执行循环：
- 当 nums[i]+nums[L]+nums[R]==0，执行循环，判断左界和右界是否和下一位置重复，去除重复解。并同时将 L,R 移到下一位置，寻找新的解
- 若和大于 0，说明 nums[R] 太大，R 左移
- 若和小于 0，说明 nums[L] 太小，L 右移
- 时间复杂度：\(O(n^2)\)
- 空间复杂度：\(O(1)\)
4.编程实现
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
class Solution{
public:
vector<vector<int>> threeSum(vector<int>& nums){
vector< vector<int> > ans;
if(nums.size() < 3 || nums.empty()) return ans; // 特判
int n = nums.size();
sort(nums.begin(), nums.end()); //排序
for(int i = 0; i < n; i++) // 枚举最小值
{
if(nums[i] > 0) return ans;
if(i > 0 && nums[i] == nums[i-1]) continue; // 最小元素去重！
int l = i+1;
int r = n-1;
while(l < r) // 枚举中间值和最大值
{
int x = nums[l] + nums[r] + nums[i];
if(x == 0){ // 符合条件，存储，并且去重，双端都移到下一个位置
ans.push_back({ nums[i], nums[l], nums[r] });
while( l < r && nums[l] == nums[l+1]) l++; l++;
while( l < r && nums[r] == nums[r-1]) r--; r--;
}
else if(x > 0) // 大了就让右边最大值变小
r--;
else // 小了就让左边中间值变大
l++;
}
}
return ans;
}
};
int main() {
int get;
Solution sol;
vector<int> nums;
getchar();
while (cin >> get) {
nums.push_back(get);
if (cin.get() == ']') break;
}
cout << sol.threeSum(nums)[0][0] << endl;
return 0;
}
无重复字符的最长子串
Leetcode：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
1.问题描述
给定一个字符串s，找出其中不含有重复字符的最长子串的长度。
2.输入输出
- Input："abcabcbb"
- Output：3
3.算法分析
滑动窗口：核心思想就是从每一个字符开始，找到不包含重复字符的最长子串。每次移动区间的起点或者终点，直到起点的值等于终点的值。
- 时间复杂度：O（n）
- 空间复杂度：O（1）
4.编程实现
#include <iostream>
#include <string>
using namespace std;
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int start(0), end(0), length(0), result(0);
int nSize = s.size();
while (end < nSize) { // 终点
char tmpChar = s[end];
for (int index = start; index < end; index++) {
if (tmpChar == s[index]) {
start = index + 1;
length = end - start;
break;
}
}
end++;
length++;
result = max(result, length);
}
return result;
}
};
int main() {
Solution sol;
string s;
cin >> s;
cout << sol.lengthOfLongestSubstring(s) << endl;
return 0;
}
合并两个有序数组
Leetcode：88，https://leetcode-cn.com/problems/merge-sorted-array/
1.问题描述
给定两个有序数组，把两个数组合并为一个，将第二个数组归并到第一个数组上，
不需要开辟额外空间。
2.输入输出
- Input：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
- Output：[1, 2, 2, 3, 5, 6]
3.算法分析
两个指针放在数组的末尾，第三个指针定义pos，每次将较大的那个数字复制到第一个数组的后面，然后向前移动一位。
- 时间复杂度：O（m+n）
- 空间复杂度：O（1）
4.编程实现
#include <iostream>
#include <vector>
using namespace std;
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n){
int pos = m-- + n-- - 1;
while(m >= 0 && n >= 0){
nums1[pos--] = nums1[m] > nums2[n]? nums1[m--]: nums2[n--];
}
while(n >= 0){
nums1[pos--] = nums2[n--];
}
}
int main(){
vector<int> nums1;
nums1.push_back(1);
nums1.push_back(2);
nums1.push_back(3);
nums1.push_back(0);
nums1.push_back(0);
nums1.push_back(0);
vector<int> nums2;
nums2.push_back(2);
nums2.push_back(5);
nums2.push_back(6);
int m = 3;
int n = 3;
merge(nums1, m, nums2, n);
cout << nums1[4] << endl;
}