1. 两数之和
给定一个整数数组 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) 的算法吗？
解决方案
- C
/** * Note: The returned array must be malloced, assume caller calls free(). */ int* twoSum(int* nums, int numsSize, int target, int* returnSize){ int* res = (int *)malloc(sizeof(int) * 2); for(int i = 0; i < numsSize - 1; i++) { for(int j = i + 1; j < numsSize; j++) { if(nums[i] + nums[j] == target) { res[0] = i; res[1] = j; *returnSize = 2; return res; } } } *returnSize = 0; return res; }
167. 两数之和Ⅱ-输入有序数组
给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。
以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。
你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。
你所设计的解决方案必须只使用常量级的额外空间。
示例 1：
输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
示例 2：
输入：numbers = [2,3,4], target = 6
输出：[1,3]
解释：2 与 4 之和等于目标数 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3] 。
示例 3：
输入：numbers = [-1,0], target = -1
输出：[1,2]
解释：-1 与 0 之和等于目标数 -1 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
提示：
2 <= numbers.length <= 3 * 104
-1000 <= numbers[i] <= 1000
numbers 按 非递减顺序 排列
-1000 <= target <= 1000
仅存在一个有效答案
解题方案
- C 双指针
/** * Note: The returned array must be malloced, assume caller calls free(). */ int* twoSum(int* numbers, int numbersSize, int target, int* returnSize) { int head = 0, tail = numbersSize - 1; // 定义双指针 int sum = 0; // 定义算术和 int* result = (int*)malloc(sizeof(int) * 2); // 申请内存 while (head < tail) { sum = numbers[head] + numbers[tail]; // 求和 if (sum == target) { result[0] = head + 1; // 得到下标 result[1] = tail + 1; *returnSize = 2; // 数组共两个元素 return result; } if (sum > target) { tail--; // 和大了，减小 } else { head++; // 和小了，增大 } } *returnSize = 2; return result; }
复杂度分析
时间复杂度为 O(n)，其中 n 为 numbers 的长度。
空间复杂度为 O(1)。
