LeetCode刷题总结-指针法

        方法介绍：指针法主要使用在一组按从小到大排好序的数组中，当按照条件查找对应元素时，在数组的前后定义两个指针，当两个指针代表的元素进行运算时：若结果大于目标值，则左移右侧的指针；若结果小于目标值，则向右移动左侧指针。因为此时序列是排好序的，当大于目标值时，左侧的指针如果向右移动时得到的结果会更大，所以此时应该左移右侧的指针而右侧指针不动，反之亦然。这样做的好处是不用两次遍历数组，把O(n2)的计算复杂的转换成了O（n）的计算复杂度。当然使用这个方法的前提是这个数组是排好序的。（代表题目：1,15,16,18）

 1. Two Sum

     题意：给定一个整形数组和目标和target，返回数组中，两个数的和等于目标和target的下标。（输入保证只有一个合法的解）

    方法：1. 暴力法(时间复杂度O（n^2）) ；2. 二分法（时间复杂度O（nlogn））； 3. 指针法

    方法一：暴力法----使用两个for的嵌套循环，遍历所有可能的组合；

 

class Solution(object):    def twoSum(self, nums, target):        """        :type nums: List[int]        :type target: int        :rtype: List[int]        """        for i in range(len(nums)-1):            for j in range(i+1,len(nums)):                if nums[i] + nums[j] == target:                    return [i,j]

 

 

 

    方法二：二分法

 

class Solution(object):    def twoSum(self, nums, target):        """        :type nums: List[int]        :type target: int        :rtype: List[int]        """        vis = {}        for i, num in enumerate(nums):            diff = target - num            if diff in vis:                return [vis[diff], i]            vis[num] = i

 

 

 

    方法三：指针法

 

15. 3Sum

题意：给定一个数组，求所有满足条件的三个数a,b,c，使得a+b+c=0  （结果要去重）

方法：指针法枚举一个数，然后双指针，时间复杂度O(n^2)，注意在查找的过程中去重。

 

class Solution:    def threeSum(self, nums: List[int]) -> List[List[int]]:        nums.sort()        n = len(nums)        ans = []        for i in range(n-2):            if i > 0 and nums[i] == nums[i - 1]:                 continue          # 去重            L, R = i + 1, n - 1            while L < R:                temp = nums[i] + nums[L] + nums[R]                if temp == 0:                    ans.append([nums[i], nums[L], nums[R]])                    L += 1                    R -= 1                    while L < R and nums[L] == nums[L - 1]:                         L += 1     #去重                    while R > L and nums[R] == nums[R + 1]:                         R -= 1     #去重                elif temp > 0:                    R -= 1                else:                    L += 1        return ans

 

 

 

18. 四数之和

题意：在一组无序数中找出四个数之和等于目标值的所有组合；

方法：枚举两个数，其余两个数使用指针法；

 

class Solution:    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:        n = len(nums)        nums.sort()        ans = []        for i in range(n - 3):            if i > 0 and nums[i] == nums[i - 1]:                 continue      # 去重            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 j in range(i + 1, n - 2):                if j > i + 1 and nums[j] == nums[j - 1]:                     continue                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                L, R = j + 1, n - 1                while L < R:                    temp = nums[i] + nums[j] + nums[L] + nums[R]                    if temp == target:                        ans.append([nums[i], nums[j], nums[L], nums[R]])                        L += 1                        R -= 1                        while L < R and nums[L] == nums[L - 1]:                             L += 1                        while R > L and nums[R] == nums[R + 1]:                             R -= 1                    elif temp > target:                        R -= 1                    else:                        L += 1        return ans