Tag Archives: 首尾指针

LeetCode 3Sum Closest

16. 3Sum Closest

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:

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

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

此题和LeetCode 3Sum类似,不过是要求一个三元组的和和target最相近,而不是等于0。思路一样,先排序,然后首尾指针向target夹逼。对于每一个外层循环,记录下该循环得到的最小diff,然后在所有diff中取最小。在遍历的过程中如果发现diff=0,直接返回target。 完整代码如下:

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target)
    {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        vector<int> diff(n, INT_MAX);
        vector<int> sum(n);
        for (int i = 0; i < n; i++) {
            if (i == 0 || nums[i] > nums[i – 1]) {
                int s = i + 1, t = n – 1;
                while (s < t) {
                    int tmp_sum = nums[i] + nums[s] + nums[t];
                    if (abs(tmp_sum – target) < diff[i]) {
                        diff[i] = abs(tmp_sum – target);
                        sum[i] = tmp_sum;
                    }
                    if (tmp_sum < target)
                        s++;
                    else if (tmp_sum > target)
                        t–;
                    else {
                        return target;
                    }
                }
            }
        }
        int min_diff = INT_MAX, ans;
        for (int i = 0; i < n; i++) {
            if (diff[i] < min_diff) {
                min_diff = diff[i];
                ans = sum[i];
            }
        }
        return ans;
    }
};

本代码提交AC,用时12MS。

二刷:
上面的代码过于复杂,其实没必要存储diff和sum,因为最终只是求一个closest,在循环中就可以保存最小值,代码如下:

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target)
    {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        if (n < 3)
            return accumulate(nums.begin(), nums.end(), 0);
        int ans = nums[0] + nums[1] + nums[2];
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1, k = n – 1; j < k;) {
                int sum = nums[i] + nums[j] + nums[k];
                if (abs(sum – target) < abs(ans – target))
                    ans = sum;
                if (sum == target)
                    return target;
                else if (sum < target)
                    ++j;
                else
                    –k;
            }
        }
        return ans;
    }
};

本代码提交AC,用时6MS。

LeetCode 3Sum

15. 3Sum

Given an array nums of n integers, are there elements abc 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:

Given array nums = [-1, 0, 1, 2, -1, -4],

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

给定一串无序的数组,找出所有不重复的三元组,其和为0。其实就是三个数加起来等于某个特定的数,这和两个数加起来等于某个特定的数是类似的。 暴力求解肯定不行$O(n^3)$。后来想到hash,把所有数hash,然后任取两个数a,b,然后查hash表,如果-(a+b)在hash表中,则找到一个三元组,此时的时间复杂度是$O(n^2)$。 完整代码如下:

class Solution {
public:
    vector<vector<int> > threeSum(vector<int>& nums)
    {
        set<vector<int> > tmp;
        int min_v = INT_MAX, max_v = INT_MIN;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] < min_v) {
                min_v = nums[i];
            }
            if (nums[i] > max_v) {
                max_v = nums[i];
            }
        }
        vector<int> hash(max_v – min_v + 1, 0);
        for (int i = 0; i < nums.size(); i++) {
            hash[nums[i] – min_v]++;
        }
        for (int i = 0; i < hash.size(); i++) {
            if (hash[i] == 0)
                continue;
            hash[i]–;
            for (int j = i; j < hash.size(); j++) {
                if (hash[j] == 0)
                    continue;
                hash[j]–;
                int sum1 = i + min_v + j + min_v;
                int idx = -sum1 – min_v;
                if (idx >= 0 && idx < hash.size() && hash[-sum1 – min_v]) {
                    vector<int> hit = { i + min_v, j + min_v, -sum1 };
                    sort(hit.begin(), hit.end());
                    tmp.insert(hit);
                }
                hash[j]++;
            }
            hash[i]++;
        }
        vector<vector<int> > ans;
        for (auto const& vi : tmp) {
            ans.push_back(vi);
        }
        return ans;
    }
};

本代码提交AC,用时108MS,排在了倒数3%的位置,说明算法还有待改进。

上述代码有两个地方值得改进。首先,每个三元组我都重新排序了,因为a,b是任意取的,导致-(a+b)的大小关系和a,b不确定,我们可以先选定a,然后等价于找两个数加起来等于-a,找的方法就是从比a大的那边找,并且b和c分别是比a大的那边的首尾指针,这样就确定了a<b<c的关系,不用担心有遗漏情况,因为如果有比a小的两个数b,c和a加起来等于0,那么在外层遍历b或c的时候就已经找到了。
第二个可改进的地方是,因为上述策略不会导致有重复的三元组出现,所以set操作也可以省略了。第二版代码如下:

class Solution {
public:
    vector<vector<int> > threeSum(vector<int>& nums)
    {
        vector<vector<int> > tmp;
        if (nums.size() < 3)
            return tmp;
        int min_v = INT_MAX, max_v = INT_MIN;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] < min_v) {
                min_v = nums[i];
            }
            if (nums[i] > max_v) {
                max_v = nums[i];
            }
        }
        vector<int> hash(max_v – min_v + 1, 0);
        for (int i = 0; i < nums.size(); i++) {
            hash[nums[i] – min_v]++;
        }
        for (int i = 0; i < hash.size(); i++) {
            if (hash[i] == 0)
                continue;
            hash[i]–;
            int s = i, t = hash.size() – 1;
            while (s <= t) {
                if (!hash[s]) {
                    s++;
                    continue;
                }
                else {
                    hash[s]–;
                }
                if (!hash[t]) {
                    t–;
                    hash[s]++;
                    continue;
                }
                else {
                    hash[t]–;
                }
                int sum1 = s + min_v + t + min_v;
                hash[s]++;
                hash[t]++;
                if (sum1 + i + min_v < 0) {
                    s++;
                }
                else if (sum1 + i + min_v > 0) {
                    t–;
                }
                else {
                    vector<int> hit = { i + min_v, s + min_v, t + min_v };
                    tmp.push_back(hit);
                    s++;
                    t–;
                }
            }
            hash[i]++;
        }
        return tmp;
    }
};

本代码提交AC,用时52MS,瞬间排在了前20%。
其实可以直接对数组排序来代替我的hash,渐进复杂度都是一样的。

二刷:
上面的代码太复杂了,简洁的做法是,先对数组排序,然后找a<b<c使得a+b+c=0,我们用i,j,k分别指向要找的a,b,c,外层循环是i尝试每个数,内存循环是在i右边的首尾指针j和k,找a[j]+a[k]=-a[i]的(j,k)对。内存循环相当于常规的2sum了。
注意要对i,j,k进行去重。完整代码如下,超简洁。

class Solution {
public:
    vector<vector<int> > threeSum(vector<int>& nums)
    {
        sort(nums.begin(), nums.end());
        vector<vector<int> > ans;
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            if (i > 0 && nums[i] == nums[i – 1])
                continue; // avoid duplicates
            for (int j = i + 1, k = n – 1; j < k;) {
                if (nums[i] + nums[j] + nums[k] == 0) {
                    ans.push_back({ nums[i], nums[j], nums[k] });
                    ++j;
                    –k;
                    while (j < k && nums[j] == nums[j – 1])
                        ++j; // avoid duplicates
                    while (j < k && nums[k] == nums[k + 1])
                        –k; // avoid duplicates
                }
                else if (nums[i] + nums[j] + nums[k] > 0) {
                    –k;
                }
                else {
                    ++j;
                }
            }
        }
        return ans;
    }
};

本代码提交AC,用时118MS。

三刷。更简单的借助hash的O(n^2)解法,hash里存储了每个数出现的次数。为了避免重复,特别需要注意nums[i]!=nums[i-1];nums[j]!=nums[j-1];且对于第三个数another,它要大于nums[j],且存在。所以这里面的数值关系是nums[i]<nums[j]<another,这样才能避免三元组重复。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> ans;
        int n = nums.size();
        unordered_map<int, int> hash;
        for(int i = 0; i < n; ++i) ++hash[nums[i]];
        for(int i = 0; i < n; ++i) {
            if(i != 0 && nums[i] == nums[i - 1]) continue;
            
            --hash[nums[i]];
            for(int j = i + 1; j < n; ++j) {
                if(j != i + 1 && nums[j] == nums[j - 1]) continue;
                
                --hash[nums[j]];
                int another = - nums[i] - nums[j];
                if(another >= nums[j] && hash[another] > 0) ans.push_back({nums[i], nums[j], another});
                ++hash[nums[j]];
            }
            ++hash[nums[i]];
        }
        return ans;
    }
};

本代码提交AC,用时800MS,效率较低。

四刷。先排序,然后固定一个数i,另外两个数j,k分别指向i右边的数组的头尾,头尾指针移动的方法找加和等于-nums[i]的数。需要对i/j/k都while去重。完整代码如下:

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        
        vector<vector<int>> ans;
        int n = nums.size();
        int i = 0;
        while(i < n - 2) {
            if(i != 0 && nums[i] == nums[i - 1]) {
                ++i;
                continue;
            }
            int target = -nums[i];
            int j = i + 1, k = n - 1;
            while(j < k) {
                if(nums[j] + nums[k] == target) {
                    vector<int> tmp = {nums[i], nums[j], nums[k]};
                    ans.push_back(tmp);
                    while(j < k && nums[j] == tmp[1]) ++j;
                    while(j < k && nums[k] == tmp[2]) --k;
                } else if (nums[j] + nums[k] > target) {
                    --k;
                } else {
                    ++j;
                }
            }
            ++i;
        }
        return ans;
    }
};

本代码提交AC,用时124MS,比用hash的方法快很多。

LeetCode Longest Substring Without Repeating Characters

3. Longest Substring Without Repeating Characters

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

Example 1:

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

Example 2:

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

Example 3:

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.

本题要求找出字符串中没有重复字母的最长连续子串。最快想到的是两重遍历i,j,每次用set判断是否重复,重复就进行下一次遍历i++,但是这样显然超时。 因为字符串中只有ASCII,所以可以用bool hash[128]来判断是否有重复字符,比set要快(用空间换时间)。
另外,假设遍历状态是abcdefgc,发现有两个’c’,下一次遍历的时候没必要从b开始遍历,因为从b开始肯定也会遇到后面的两个’c’,但此时字符串长度比之前的少1,所以可以直接从上次的’c’的下一个字母’d’开始重新遍历,这样可以节省不少时间。
完整代码如下:

class Solution {
public:
    int lengthOfLongestSubstring(string s)
    {
        int longest = 0, n = s.size(), cur = 0;
        vector<int> hash(128, 0);
        for (int i = 0; i < n; i++) {
            if (hash[s[i]]) {
                if (cur > longest)
                    longest = cur;
                cur = 0;
                i = hash[s[i]]; //从重复字符下一个字符开始遍历
                //memset(&hash[0], 0, 128*sizeof(int));//比fill更快,但是没fill安全
                fill(hash.begin(), hash.end(), 0);
            }
            hash[s[i]] = i + 1; //记录下一个字符下标
            cur++;
        }
        return (longest > cur) ? longest : cur;
    }
};

本代码提交AC,用时68MS。
二刷,上面我的解法太过复杂。其实我们可以用一个map保存出现字符的最大下标,start保存一个下标,使得从start到当前字符这个区间不存在重复字符。
每来一个字符,我们去map中找一下,如果该字符之前存在,则更新start为最大下标(为了满足从start到当前字符这个区间不存在重复字符),然后不重复子串的长度就是i-start。
完整代码如下,因为s只包含字符,所以也可以用一个256长的数组表示map。

class Solution {
public:
    int lengthOfLongestSubstring(string s)
    {
        map<char, int> visited;
        int ans = 0, start = -1;
        for (int i = 0; i < s.size(); ++i) {
            if (visited.find(s[i]) != visited.end())
                start = max(start, visited[s[i]]);
            visited[s[i]] = i;
            ans = max(ans, i – start);
        }
        return ans;
    }
};

本代码提交AC,用时22MS。

三刷。首尾指针法,令[i,j)为不含重复字符的子串的区间,用一个hash数组存储某个字符是否出现过。开始的时候,j不断往前走,直到遇到区间[i,j)中出现过的字符,假设这个字符下标为k的话,则需要把[i,k]之间的hash全部重置为0,i跳到k+1,此后j继续往前走。

完整代码如下:

class Solution {
public:
	int lengthOfLongestSubstring(string s) {
		int n = s.size();
		if (n == 0 || n == 1)return n;
		vector<int> hash(256, 0);
		int i = 0, j = 1;
		hash[s[0]] = 1;
		int ans = 0;
		while (j < n) {
			while (j < n&&hash[s[j]] == 0) {
				hash[s[j]] = 1;
				++j;
			}
			if (j - i > ans)ans = j - i;
			if (hash[s[j]] == 1) {
				while (s[i] != s[j]) {
					hash[s[i]] = 0;
					++i;
				}
				hash[s[i]] = 0;
				++i;
			}
		}
		return ans;
	}
};

本代码提交AC,用时8MS,虽然比解法2快,但解法2代码最简单了。

LeetCode Two Sum

1. Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

开学课业压力好大,已经有两个月没有刷题了,现在开始LeetCode,从#1开始! 这一题要从一个序列中找出两数之和为target的两个数。因为序列无序,所以能够想到的最简单的方法就是先对数组排序,然后设置头尾两个指针,判断求和情况和target的大小关系。当得到两个数之后,再在原序列中找这两个数的index,注意index1<index2。 完整代码如下:

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target)
    {
        vector<int> nums_copy = nums;
        sort(nums_copy.begin(), nums_copy.end());
        int i = 0, j = nums_copy.size() – 1;
        while (i != j) {
            if (nums_copy[i] + nums_copy[j] == target)
                break;
            else if (nums_copy[i] + nums_copy[j] < target)
                i++;
            else
                j--;
        }
        vector<int> ans(2);
        for (int k = 0; k < nums.size(); k++) {
            if (ans[0] == 0 && nums[k] == nums_copy[i])
                ans[0] = k + 1;
            else if (ans[1] == 0 && nums[k] == nums_copy[j])
                ans[1] = k + 1;
        }
        if (ans[0] > ans[1])
            swap(ans[0], ans[1]);
        return ans;
    }
};

本代码提交AC,用时16MS。
还可以借助hash方法实现O(n)的算法。思路是将nums全部hash存储,然后扫描数组,判断target-nums[i]是否在hash表中。整个运行时间在O(n)。
代码如下:

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target)
    {
        //map<int, int> nums_index;
        unordered_map<int, int> nums_index; // unordered_map比map快
        vector<int> ans(2);
        for (int i = 0; i < nums.size(); i++) {
            int added = target – nums[i];
            if (nums_index.find(added) != nums_index.end()) {
                ans[0] = nums_index[added];
                ans[1] = i + 1;
                return ans;
            }
            nums_index[nums[i]] = i + 1;
        }
    }
};

本代码提交AC,用时还是16MS。
此题测试数据只有16组,真是太少了,如果数据多的话,相信第二种方法会快很多。