【LeetCode刷题】-数之和专题（待补充更多题目）

1 两数之和

1 两数之和
思路：hush map

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hush=[]
        for i in range(len(nums)):
            temp=target-nums[i]
            if temp in hush:
                return [hush.index(temp),i]
            else:
                hush.append(nums[i])

附一个画蛇添足的错误解法：
题目要求返回的是 index ，就不适用这种一上来就 sort 的解法，
由于nums中有重复元素的存在，这种方法不出意外地报错了。

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        temp1=nums.copy()
        nums.sort()
        l,r=0,len(nums)-1
        while l<r:
            temp=nums[l]+nums[r]
            if temp==target:
                return [temp1.index(nums[l]),temp1.index(nums[r])]
            elif temp<target:
                l+=1
            else:
                r-=1

15 三数之和

15 三数之和
思路：sort 之后用双指针
三数之和题解（其中一种超时了）

18 四数之和

[18 四数之和](https://leetcode.cn/problems/4sum/
思路：还是sort 之后双指针

# TODO:加上代码

633 平方数之和

633 平方数之和
这个题挺简单的，确定检索范围是 range(1, int(math.sqrt(c) + 1)),
在这个范围内找两个数，使得它们的平方和是目标值，
接下来就是经典的两数和问题了。

Python 开方：math.sqrt(num)

解法1：双指针法

class Solution(object):
    def judgeSquareSum(self, c):
        if c == 0: return True
        n=int(math.sqrt(c))
        a,b=0,n
        while a<=b:
            temp=c-a**2-b**2
            if temp ==0:
                return True
            elif temp>0:
                a+=1
            else:
                b-=1
        return False

解法2：暴力计算
注：因为只要b是自然数就符合题目要求，所以就不用辛辛苦苦地遍历list了，直接判断b是否是整数。

判断某数是否为整数：int(num)==num

class Solution(object):
    def judgeSquareSum(self, c):
        if c == 0: return True
        for a in range(1, int(math.sqrt(c) + 1)):
            b = c - a * a
            if int(math.sqrt(b)) ** 2 == b:
                return True
        return False

关于双指针的一点思考

双指针的本质是什么？
移动的时候会不会剪掉正确答案？

珠玉在前，放个大神写的关于双指针的解析