数组的定义
在这里插入图片描述
数组的存储
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
学习视频
数组问题，如果想快的话 要是排序数组，使用双指针，二分查找法，哈希表法等
例题
两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
暴力查找
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
length = len(nums)
for i in range(length-1):
for j in range(i+1, length):
if nums[i] + nums[j] == target:
return [i, j]
return []
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int n = nums.size();
for(int i=0; i<n-1; i++)
{
for(int j=i+1; j<n; j++)
{
if(nums[i] + nums[j]==target)
{
return {i, j};
}
}
}
return {};
}
};
哈希表
遍历一遍后，再从字典中找，时间复杂度为O(1)
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
hashtable = dict()
for i, num in enumerate(nums):
if target-num in hashtable:
return [hashtable[target-num], i]
hashtable[nums[i]] = i
return []
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> hashtable;
int n = nums.size();
for(int i=0; i<n; i++)
{
auto it = hashtable.find(target-nums[i]);
if(it != hashtable.end())
{
return {it->second, i};
}
hashtable[nums[i]] = i;
}
return {};
}
};
最接近的三数之和
给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。
返回这三个数的和。
假定每组输入只存在恰好一个解。
暴力解法
class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
n = len(nums)
error = float('inf')
sum = 0
for i in range(n-2):
for j in range(i+1, n-1):
for k in range(j+1, n):
if abs(nums[i] + nums[j] + nums[k]-target) < error:
sum = nums[i] + nums[j] + nums[k]
error = abs(sum-target)
return sum
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
double error = INT_MAX;
int sum = 0;
int n = nums.size();
for(int i=0; i<n-2; i++)
{
for(int j=i+1; j<n-1; j++)
{
for(int k=j+1; k<n; k++)
{
if(abs(nums[i]+nums[j]+nums[k]-target) < error)
{
sum = nums[i] + nums[i] + nums[k];
error = abs(nums[i]+nums[j]+nums[k]-target);
}
}
}
}
return sum;
}
};
先排序，再通过双指针遍历
class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
length = len(nums)
nums.sort()
result = nums[0] + nums[1] + nums[2]
for i in range(length):
start = i + 1
end = length - 1
while start < end:
sum = nums[i] + nums[start] + nums[end]
if abs(target-sum) < abs(target-result):
result = sum
if sum > target:
end -= 1
elif sum < target:
start += 1
else:
return result
return result
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
int n = nums.size();
sort(nums.begin(), nums.end());
int result = nums[0] + nums[1] + nums[2];
int error = INT_MAX;
for(int i=0; i<n-2; i++)
{
int start = i+1;
int end = n-1;
while(start < end)
{
int sum = nums[i] + nums[start] + nums[end];
if(abs(target-sum) < abs(target-result))
{
result = sum;
}
if(sum > target)
{
end--;
}
else if(sum < target)
{
start++;
}
else
return result;
}
}
return result;
}
};
删除有序数组中的重复项
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
对于有序数组，且在原地操作的话，一般是使用双指针方法，前后一个快慢指针
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
n = len(nums)
if not nums:
return 0;
slow = fast = 1
while fast < n:
if nums[fast] != nums[fast-1]:
nums[slow] = nums[fast]
slow += 1
fast += 1
return slow
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int n = nums.size();
int slow = 1;
int fast = 1;
while(fast < n)
{
if(nums[fast] != nums[fast-1])
{
nums[slow] = nums[fast];
slow++;
}
fast++;
}
return slow;
}
};
移除元素
给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
一样可以使用双指针算法进行解决，可以知道重复元素是挨着出现的，定义两个指针进行遍历
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
n = len(nums)
if not n:
return 0
slow = 0
fast = 0
while fast < n:
if nums[fast] != val:
nums[slow] = nums[fast]
slow += 1
fast += 1
return slow
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int n = nums.size();
if(not n)
{
return 0;
}
int slow = 0;
int fast = 0;
while(fast<n)
{
if(nums[fast] != val)
{
nums[slow] = nums[fast];
slow++;
}
fast++;
}
return slow;
}
};
双指针也可以两个开始，i+1和最右端， 将最右端的值赋值给左边，基于相应的关系更新左右指针
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int n = nums.size();
if(not n)
{
return 0;
}
int left = 0;
int right = n-1;
while(left <= right)
{
if(nums[left] == val)
{
nums[left] = nums[right];
right--;
}
else
{
left++;
}
}
return left;
}
};
三数之和
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
先排序，再定第一个数，第三个数总是从最右边往左走，第二个数从第一个数的右边开始走
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
res = []
if n < 3:
return res
nums.sort()
for first in range(n-2):
if first > 0 and nums[first] == nums[first-1]: # 需要和上次枚举的方法不一样
continue
if nums[first] > 0: # 第一个数大于0时候不用再遍历下去
break
# 第三个数
third = n-1
target = 0 - nums[first]
# 枚举第二个数
for second in range(first+1, n-1):
# 需要和上次枚举的数不同
if second > first + 1 and nums[second] == nums[second-1]:
continue
# 需要保证第二个数的指针在第三个数的指针的左侧
while second < third and nums[second] + nums[third] > target:
third -= 1
if second == third:
break
if nums[second] + nums[third] == target:
res.append([nums[first], nums[second], nums[third]])
return res
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
int n = nums.size();
if(n<3)
{
return {};
}
sort(nums.begin(), nums.end());
vector<vector<int>> ans;
for(int first=0; first<n-2; first++)
{
if(nums[first] > 0)
{
break;
}
if(first > 0 && nums[first] == nums[first-1])
{
continue;
}
int target = -nums[first];
int third = n - 1;
for(int second=first+1; second<n-1; second++)
{
if(second>first+1 && nums[second]==nums[second-1])
{
continue;
}
while(second < third && nums[second]+nums[third] >target)
{
--third;
}
if(second == third)
{
break;
}
if(nums[second]+nums[third] == target)
{
ans.push_back({nums[first], nums[second], nums[third]});
}
}
}
return ans;
}
};
