Monthly Archives: March 2016

LeetCode 3Sum Closest

LeetCode 3Sum Closest
Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

    For example, given array S = {-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

LeetCode 3Sum
Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note:

  • Elements in a triplet (a,b,c) must be in non-descending order. (ie, abc)
  • The solution set must not contain duplicate triplets.
    For example, given array S = {-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。