第五天

双指针求解

Python：

#Python：
#	双指针法求解：正常情况要想从列表中获取三个元素并求和需要三重循环
#	而双指针则可以在两层循环里完成，即定一移二
#	首先定义一个指针（当然Python里没有指针的概念，只是我自己习惯这么称呼）
#	从起始位置记录数据，在他的后面定义两个指针分别指向末尾和该指针的下一位
#	从而可以在较短时间内从列表中通过两层循环遍历得到三个数据并进行相关操作
#	（注：后面两个指针的相对关系及其变化规律需要多加注意）

class Solution:    
	def threeSumClosest(self, nums: List[int], target: int) -> int:        
		res = 0        
		min1 = float('inf')        #设置min1为正无穷大
					   #负无穷大 -float('inf') // float('-inf')
		nums.sort()        
		for i in range(len(nums) - 2):            
			l = i + 1            
			r = len(nums) - 1            
			while l < r:                
				num = nums[i] + nums[l] + nums[r]                
				if abs(num - target) < abs(min1):                    
					min1 = num - target                    
					res = num                
				if num - target == 0:                    
					return target                
				elif num - target > 0:                    
					r -= 1                
				else:                    
					l += 1        
		return res
	#当然，这个代码只是为了说明双指针遍历列表，还可以进行简单的优化使其速度更快。

---

c++：

class Solution {
public:    
	int threeSumClosest(vector<int>& nums, int target) {
		sort(nums.begin(), nums.end());        				        
		int min1 = 100000, res = 0;        
		vector<int>::iterator it, l, r;        
		for (it = nums.begin(); it != nums.end(); it++)        
		{            
			l = it + 1;            
			r = nums.end() - 1;            
			while (l < r)            
			{                
				int num = *it + *l + *r;                
				if (abs(num - target) < abs(min1))                
				{                    
					res = num;                    
					min1 = num - target;                
				}                
				if (num - target == 0)  return target;                
				else if ((num - target) > 0)    --r;                
				else    ++l;            
			}        
		}        
		return res;    
	}
};