【leetcode top100】两数相加。无重复字符的最长子串，盛水最多的容器，三数之和
目录
2. 两数相加 - 力扣（LeetCode）
3. 无重复字符的最长子串 - 力扣（LeetCode）
11. 盛最多水的容器 - 力扣（LeetCode）
15. 三数之和 - 力扣（LeetCode）
2. 两数相加 - 力扣（LeetCode）
思路：使用双指针在两个链表上遍历相加，注意进位的问题。（python and c++）
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
dummpyHead = ListNode(-1)
cur = dummpyHead
tmp,bit,v1,v2 = 0,0,0,0
while l1 or l2:
v1 = l1.val if l1 else 0
v2 = l2.val if l2 else 0
tmp = v1 + v2 + bit
dummpyHead.next = ListNode(tmp % 10)
dummpyHead = dummpyHead.next
bit = tmp // 10
if l1: l1 = l1.next
if l2: l2 = l2.next
if bit > 0:
dummpyHead.next = ListNode(bit)
return cur.next
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* dummpHead = new ListNode(-1);
ListNode* cur = dummpHead;
int tmp = 0,bit = 0,v1 = 0,v2 = 0;
while (l1 || l2){
v1 = l1 ? l1->val : 0;
v2 = l2 ? l2->val : 0;
tmp = v1 + v2 + bit;
dummpHead->next = new ListNode(tmp % 10);
dummpHead = dummpHead->next;
bit = tmp / 10;
if (l1) l1 = l1->next;
if (l2) l2 = l2->next;
}
if (bit > 0) dummpHead->next = new ListNode(bit);
return cur->next;
}
};3. 无重复字符的最长子串 - 力扣（LeetCode）
思路：滑动窗口。维护一个集合，将遍历得到的char判断是否在集合中，若在集合中，从左边开始删除元素，一直删除到没有重复元素（使用while），若元素不在集合中，将元素放入到集合中，维护窗口中最多元素数量，当前元素数量，和最左端下标（用来删除元素）。
class Solution {
public:
int lengthOfLongestSubstring(string s) {
// 滑动窗口
if (s.empty()) return 0;
unordered_set<char> window;
int maxLen = 0,curLen = 0,idx = 0;
int size = s.length();
for (int i = 0;i < size;i++){
curLen++;
while (window.find(s[i]) != window.end()){
window.erase(s[idx]);
idx++;
curLen--;
}
window.insert(s[i]);
maxLen = max(maxLen,curLen);
}
return maxLen;
}
};class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
# 滑动窗口
if not s:return 0
maxLen,curLen,idx = 0,0,0
window = set()
for num in s:
curLen += 1
while num in window:
window.remove(s[idx])
idx += 1
curLen -= 1
window.add(num)
maxLen = max(maxLen,curLen)
return maxLen
注意：python中集合删除元素不能使用pop(),因为pop（）是随机删除元素。
11. 盛最多水的容器 - 力扣（LeetCode）
思路：使用双指针left 和right,维护一个最大值，不断的移动指针，重点在于移动指针的逻辑，看left 和right指针指向的值，移动指向值小的指针。（python and c++）
class Solution {
public:
int maxArea(vector<int>& height) {
// 双指针解法
int n = height.size();
if (n < 2) return 0;
int left = 0,right = n-1;
int maxVolume = 0,volume = 0;
while (left < right){
volume = min(height[left],height[right]) * (right-left);
maxVolume = max(maxVolume,volume);
if (height[left] > height[right]) right--;
else left++;
}
return maxVolume;
}
};
class Solution:
def maxArea(self, height: List[int]) -> int:
# 双指针
# 边界
n = len(height)
if n < 2:return 0
# 定义指针
left,right = 0,n-1
volume = 0
while left < right:
volume = max((min(height[left],height[right]) * (right-left)),volume)
if height[left] < height[right]:
left += 1
else:right -= 1
return volume时间复杂度：O(n).双指针总共遍历数组一次；
空间复杂度：O(1). 只需要常数级别的空间、
注意：在if-else语句中，else是不能随便省略的，当if (A)为真或者为假时，需要进行处理的时候，就不能省略else关键字，如果对A的真假判断之后不需要处理，则可以省略掉else关键字。
15. 三数之和 - 力扣（LeetCode）
思路：挖坑（现在还不是很明白）
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
# 排序+双重循环
n = len(nums)
if n < 3:return []
nums.sort()
ans = []
for i in range(n):
if i > 0 and nums[i] == nums[i-1]:continue
k = n-1
for j in range(i+1,n):
if j > i+1 and nums[j] == nums[j-1]:continue
while j < k and nums[j] + nums[k] > -nums[i]:
k -= 1
if j == k: break
if nums[j] + nums[k] == -nums[i]:
ans.append([nums[i],nums[j],nums[k]])
return ansclass Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
// 排序+双重循环
vector<vector<int>> ans;
int n = nums.size();
if (n < 3) return ans;
sort(nums.begin(),nums.end());
for (int i = 0;i < n;i++){
if (i > 0 && nums[i] == nums[i-1]) continue;
int k = n-1;
for (int j = i+1;j < n;j++){
if (j > i+1 && nums[j] == nums[j-1]) continue;
while (j < k && nums[i] + nums[j] + nums[k] > 0) k--;
if (k == j) break;
if (nums[i] + nums[j] + nums[k] == 0) ans.push_back({nums[i],nums[j],nums[k]});
}
}
return ans;
}
};注意：第三个数字的下标k，应该在第一个循环中定义，不能在循环外面定义，因为第一个数字i每更新一次，就要从最右端开始遍历。