【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 ans

class Solution {
public:
    vectorint>> threeSum(vector<int>& nums) {
        // 排序+双重循环
        vectorint>> 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每更新一次，就要从最右端开始遍历。