LC3 Longest Substring Without Repeating Characters

Problem

Given a string, find the length of the longest substring without repeating characters.

Example 1:

1
2
3
Input: "abcabcbb"
Output: 3 
Explanation: The answer is "abc", with the length of 3.

Example 2:

1
2
3
Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

1
2
3
4
Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3. 
             Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
Think

滑动窗口法，设窗口为(i, j]，则遍历字符串，设置一个hashmap保存所有字符出现的位置

假如当前字符出现过，则需要将窗口的左边界移到上一次出现的位置；

然后更新res = max(res, j - i)，并将当前字符和位置保存到hashmap里

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
int lengthOfLongestSubstring(string s) {
    int n = s.size();
    int i = -1, res = 0;
    unordered_map<char, int> map;
    for(int j = 0; j < n; j++){
        if(map.count(s[j])){
            i = max(i, map[s[j]]);
        }
        res = max(res, j - i);
        map[s[j]] = j;
    }
    return res;
}

LC15 3Sum

Problem

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:

1
2
3
4
5
6
7
Given array nums = [-1, 0, 1, 2, -1, -4],

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

主要的想法是固定一个，求另外两个。为确保不重复，首先对数组排序，假设a最小，则a只能出现在<=0的部分；

剩下部分即为用双指针求解b+c=-a的所有b和c（对每一个可能的a），注意判断重复值

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
25
26
vector<vector<int>> threeSum(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    int n = nums.size();
    vector<vector<int>> res;
    for(int i = 0; i < n && nums[i] <= 0; i++){
        if(i == 0 || nums[i] != nums[i - 1]){
            helper(nums, i, res);
        }
    }
    return res;
}
void helper(vector<int>& nums, int i, vector<vector<int>>& res){
    int l = i + 1, r = nums.size() - 1;
    while(l < r){
        int sum = nums[i] + nums[l] + nums[r];
        if(sum < 0 || (l > i + 1 && nums[l] == nums[l - 1])){
            l++;
        }
        else if(sum > 0 || (r < nums.size() - 1 && nums[r] == nums[r + 1])){
            r--;
        }
        else{
            res.push_back({nums[i], nums[l++], nums[r--]});
        }
    }
}

LC16 3Sum Closest

Problem

Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

Example:

1
2
3
Given array nums = [-1, 2, 1, -4], and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
Think

和上一题3Sum的想法类似，使用的也是固定一个，求另外两个的方法

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
int threeSumClosest(vector<int>& nums, int target) {
    int n = nums.size();
    if(n < 3) return 0;
    sort(nums.begin(), nums.end());
    int res = nums[0] + nums[1] + nums[2];
    for(int first = 0; first < n - 2; first++){
        int second = first + 1;
        int third = n - 1;
        while(second < third){
            int sum = nums[first] + nums[second] + nums[third];
            if(sum == target) return target;
            if(abs(target - sum) < abs(target - res)) {
                res = sum;
            }
            if(sum < target){
                second++;
            }
            else{
                third--;
            }
        }
    }
    return res;
}

LC18 4Sum

Problem

Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:

The solution set must not contain duplicate quadruplets.

Example:

1
2
3
4
5
6
7
8
Given array nums = [1, 0, -1, 0, -2, 2], and target = 0.

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

依然是和3Sum类似的想法，先固定一个，然后对剩下的数组用3Sum的算法即可；注意剪枝条件。

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
25
26
27
28
29
30
31
32
vector<vector<int>> fourSum(vector<int>& nums, int target) {
    sort(nums.begin(), nums.end());
    int n = nums.size();
    vector<vector<int>> res;
    for(int i = 0; i < n - 3; i++){
        if(nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) break;
        if(nums[i] + nums[n - 3] + nums[n - 2] + nums[n - 1] < target) continue;
        for(int j = i + 1; j < n - 2; j++){
            if(nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) break;
            if(nums[i] + nums[j] + nums[n - 2] + nums[n - 1] < target) continue;
            if((i == 0 || nums[i] != nums[i - 1]) && (j == i + 1 || nums[j] != nums[j - 1])){
                helper(nums, i, j, res, target);
            }
        }    
    }
    return res;
}
void helper(vector<int>& nums, int i, int j, vector<vector<int>>& res, int target){
    int l = j + 1, r = nums.size() - 1;
    while(l < r){
        int sum = nums[i] + nums[j] + nums[l] + nums[r];
        if(sum < target || (l > j + 1 && nums[l] == nums[l - 1])){
            l++;
        }
        else if(sum > target || (r < nums.size() - 1 && nums[r] == nums[r + 1])){
            r--;
        }
        else{
            res.push_back({nums[i], nums[j], nums[l++], nums[r--]});
        }
    }
}

LC19 Remove Nth Node From End of List

Problem

Given a linked list, remove the n-th node from the end of list and return its head.

Example:

1
2
3
Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:

Given n will always be valid.

Follow up:

Could you do this in one pass?

Think

双指针

快指针先走n步，然后快慢指针同步向后走，直到快指针到达链表的尾端

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode* tmp = new ListNode(0);
    tmp->next = head;
    ListNode* first = tmp;
    ListNode* second = tmp;
    for(int i = 0; i <= n; i++){
        first = first->next;
    }
    while(first != NULL){
        first = first->next;
        second = second->next;
    }
    second->next = second->next->next;
    return tmp->next;
}

LC26 Remove Duplicates from Sorted Array

Problem

Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

Example 1:

1
2
3
4
5
Given nums = [1,1,2],

Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively.

It doesn't matter what you leave beyond the returned length.

Example 2:

1
2
3
4
5
Given nums = [0,0,1,1,1,2,2,3,3,4],

Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively.

It doesn't matter what values are set beyond the returned length.

Clarification:

Confused why the returned value is an integer but your answer is an array?

Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.

Internally you can think of this:

1
2
3
4
5
6
7
8
// nums is passed in by reference. (i.e., without making a copy)
int len = removeDuplicates(nums);

// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
    print(nums[i]);
}
Think

设置offset，当读到相同的数字的时候offset自增，然后将nums[i]处的数字放在nums[i - offset]处；

最后返回长度为n-offset。

Code 
1
2
3
4
5
6
7
8
9
10
11
12
int removeDuplicates(vector<int>& nums) {
    int offset = 0, n = nums.size();
    int i = 1;
    while(i < n){
        if(nums[i] == nums[i - 1]){
            offset++;
        }
        nums[i - offset] = nums[i];
        i++;
    }
    return n - offset;
}

LC27 Remove Element

Problem

Given an array nums and a value val, remove all instances of that value in-place and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

The order of elements can be changed. It doesn’t matter what you leave beyond the new length.

Example 1:

1
2
3
4
5
Given nums = [3,2,2,3], val = 3,

Your function should return length = 2, with the first two elements of nums being 2.

It doesn't matter what you leave beyond the returned length.

Example 2:

1
2
3
4
5
6
7
Given nums = [0,1,2,2,3,0,4,2], val = 2,

Your function should return length = 5, with the first five elements of nums containing 0, 1, 3, 0, and 4.

Note that the order of those five elements can be arbitrary.

It doesn't matter what values are set beyond the returned length.

Clarification:

Confused why the returned value is an integer but your answer is an array?

Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.

Internally you can think of this:

1
2
3
4
5
6
7
8
// nums is passed in by reference. (i.e., without making a copy)
int len = removeElement(nums, val);

// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
    print(nums[i]);
}
Think

类似上一题，但是注意当值不相等时才写入，相等则不写入

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int removeElement(vector<int>& nums, int val) {
    int offset = 0, n = nums.size();
    int i = 0;
    while(i < n){
        if(nums[i] == val){
            offset++;
        }
        else{
            nums[i - offset] = nums[i];
        }
        i++;
    }
    return n - offset;
}

Review

双指针一般是两种情况：

  • 两个指针之间存在差值关系或者倍数关系，一般这种关系正是题目中的核心要求；
  • 两个指针分别从数组的一头一尾进行遍历，直到两者相遇，一般这种情况多出现在有序数组，或者存在某种逻辑关系（一般不会直接给出）使得我可以选择是左边的指针右移还是右边的指针左移