考察点
题目:
给定一个整数数组
nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例
示例 1：
输入：nums = [2,7,11,15], target = 9 输出：[0,1] 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
输入：nums = [3,2,4], target = 6 输出：[1,2]
示例 3：
输入：nums = [3,3], target = 6 输出：[0,1]
提示
2 <= nums.length <= 104
109 <= nums[i] <= 109
109 <= target <= 109
- 只会存在一个有效答案
进阶
想出一个时间复杂度小于
O(n2) 的算法参考答案
嵌套循环版本
- 对列表排序过程中, 保留列表元素对应初始索引
- nums_index_sorted = sorted([(i, nums[i]) for i in range(len(nums))], key=lambda item: item[1])
- 排序后将大于target的元素部分不考虑遍历(默认元素为正的情况下)
- 双层循环访问列表
一层循环版本
- 将列表切割为两部分, 通过判断target - nums[i] 是否在nums[i+1:]中来判断是否有两数和为target.
- nums[i+1:]列表中元素索引j在原列表中索引为j+i+1