力扣Leetcode1 | 两数之和（Two Sum）

今天药忘吃喽~ 2022-12-13 11:24 131阅读 0赞

### 目录 ###

*  暴力法、一次哈希表和两次哈希表法
 *  双指针法
 *  扩展

# 暴力法、一次哈希表和两次哈希表法 #

[https://blog.csdn.net/zhushaojiecumt/article/details/102846196][https_blog.csdn.net_zhushaojiecumt_article_details_102846196]  
视频：  
[https://www.bilibili.com/video/BV1Li4y1E7gT?p=1][https_www.bilibili.com_video_BV1Li4y1E7gT_p_1]

# 双指针法 #

如果列表是无序的，需要先排序，使用双指针，分别指向头、尾。如果两数之和大于target，尾指针前移，如果两数之和小于target，首指针后移。

class Solution:
        def twoSum(self, nums: List[int], target: int) -> List[int]:
            r=zip(nums,range(len(nums)))
            r = sorted(r, key=lambda x:x[0])
            i, j=0,len(nums)-1
            while i<j:
                sum=r[i][0]+r[j][0]
                if sum<target:
                    i+=1
                elif sum>target:
                    j-=1
                else:
                    break
            return [r[i][1],r[j][1]]

[leetcode——两数之和（暴力，一遍hash，两遍hash，双指针）][leetcode_hash_hash]

nums = list(enumerate(nums))
    nums.sort(key = lambda x:x[1])
    i,j = 0, len(nums)-1
    while i < j:
        if nums[i][1] + nums[j][1] > target:
            j -= 1
        elif nums[i][1] + nums[j][1] < target:
            i += 1
        else:
            if nums[j][0] < nums[i][0]:
                nums[j],nums[i] = nums[i],nums[j]
            return num[i][0],nums[j][0]

[https://zhuanlan.zhihu.com/p/203068013][https_zhuanlan.zhihu.com_p_203068013]

[双指针（方法合集） 逐行解释 python3][_ python3]

# 扩展 #

假如不能用现成的hashMap结构，如何自己实现？  
双指针法适用的问题有哪些？  
两数之和、（接近）三数之和、四数之和的问题？

[【leetcode 逐题讲解】 0001 Two sum 力扣 两数之和，讲解了如何实现hashMap][leetcode _ 0001 Two sum _ _hashMap]

[双指针法(N数之和)][N]  
[【python-leetcode15-双指针】最接近的三数之和][python-leetcode15-]

[两数之和(two sum)问题通用解法(map法和双指针)][two sum_map]

[两数之和——双指针法][Link 1]

[Python|双指针解决三数之和问题][Python]

[https_blog.csdn.net_zhushaojiecumt_article_details_102846196]: https://blog.csdn.net/zhushaojiecumt/article/details/102846196
[https_www.bilibili.com_video_BV1Li4y1E7gT_p_1]: https://www.bilibili.com/video/BV1Li4y1E7gT?p=1
[leetcode_hash_hash]: https://www.cnblogs.com/sunupo/p/13419053.html
[https_zhuanlan.zhihu.com_p_203068013]: https://zhuanlan.zhihu.com/p/203068013
[_ python3]: https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/solution/shuang-zhi-zhen-fang-fa-he-ji-zhu-xing-jie-shi-pyt/
[leetcode _ 0001 Two sum _ _hashMap]: https://www.bilibili.com/video/BV1Ht4y1Q7Yp?from=search&seid=14391808369731189403
[N]: https://blog.csdn.net/qq_28739961/article/details/108927640?utm_medium=distribute.pc_relevant.none-task-blog-utm_term-3&spm=1001.2101.3001.4242
[python-leetcode15-]: https://www.cnblogs.com/xiximayou/p/12318903.html
[two sum_map]: https://blog.csdn.net/fat_cai_niao/article/details/103688772
[Link 1]: https://blog.csdn.net/z2431435/article/details/107464622?utm_medium=distribute.pc_aggpage_search_result.none-task-blog-2~all~sobaiduend~default-2-107464622.nonecase&utm_term=%E4%B8%A4%E6%95%B0%E4%B9%8B%E5%92%8C%E5%8F%8C%E6%8C%87%E9%92%88&spm=1000.2123.3001.4430
[Python]: https://blog.csdn.net/gschen_cn/article/details/107171781