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]
算法分析： 首先我们将两数之和改为知道 和 和 一个加数，求另一个加数是否存在的问题
这里使用了暴力破解
C
int* twoSum(int* nums, int numsSize, int target, int* returnSize){
int *arr = NULL; // 定义空整形数组
for(int i=0;i<numsSize;i++){ // 遍历数字数组
for (int j=i+1;j<numsSize;j++){ // 遍历当前数之后的数组剩余部分
if (nums[i] + nums[j] == target){ // 若两数相加等于target
arr = (int*)malloc(sizeof(int)*2); // 分配两个整形空间
arr[0] = i;
arr[1] = j;
*returnSize = 2; // 数组长度为2
return arr;
}
}
}
return arr;
}
Python
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
pos = {}
for index,num in enumerate(nums):
a_num = target - num
if a_num in pos:
return [pos[a_num],index]
pos[num] = index
return None
2.搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法
示例 1:
输入: nums = [1,3,5,6], target = 5 输出: 2 示例 2:
输入: nums = [1,3,5,6], target = 2 输出: 1 示例 3:
输入: nums = [1,3,5,6], target = 7 输出: 4
算法分析：
首先我们需要手动排除当target小于等于数组第一个、大于数组最后一个的情况
if(target <= nums[0]){
return 0;
}
if(target > nums[numsSize-1]){
return numsSize;
}
排除后，算法就具有通用性了
我们遍历数组挨个与target对比，若当前数字大于等于target，返回其下标就可以了
int searchInsert(int* nums, int numsSize, int target){
if(target <= nums[0]){
return 0;
}
if(target > nums[numsSize-1]){
return numsSize;
}
for (int j=1;j<numsSize;j++){
if(nums[j] >= target){
return j;
}
}
return 0;
}
PS：以上题目均来自LeetCode
数组版权声明：如无特殊说明，文章均为本站原创，转载请注明出处
本文链接：https://www.yangyingqi.com/52.html
