LeetCode brush question array
1, Array
1.1 definition of array
An array is a collection of several objects with a certain order. The objects that make up the array are called array elements. Where the vector corresponds to a one-dimensional array and the matrix corresponds to a two-dimensional array.
1.2 storage characteristics of array
- Arrays are stored sequentially in memory
- Two dimensional arrays are allocated according to rows (C, C + +, C #)
- The array name represents the first address of the array and is a constant
2, Brush questions
2.1 sum of two numbers
Given an integer array nums and an integer target value target, please find the two integers with and as the target value target in the array and return their array subscripts.
You can assume that each input will correspond to only one answer. However, the same element in the array cannot appear repeatedly in the answer.
You can return answers in any order.
Example 1:
Input: num = [2,7,11,15], target = 9
Output: [0,1]
Explanation: because num [0] + num [1] = = 9, return [0, 1].
Example 2:
Input: num = [3,2,4], target = 6
Output: [1,2]
Example 3:
Input: num = [3,3], target = 6
Output: [0,1]
Tips:
2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
There will only be one valid answer
Advanced: can you think of an algorithm with less time complexity than O(n2)?
2.1.1 solution 1 violence enumeration
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
answer = []
for i in range(len(nums)):#First value
for j in range(i+1,len(nums)):#Because a+b==b+a, the second value comes after the first value
if(nums[i]+nums[j]==target):#Is it equal to the value to be found
answer.append(i)
answer.append(j)
return answer#Join the index and return
#2836 ms 15.3 MB
#Advantages: simple and easy to understand
#Disadvantages: time complexity is O (n2)
2.1.2 solution 2 change the index of the array, keep the value unchanged, and query whether the corresponding value (target Num) of each element exists.
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
hashMap = {}#Use the dictionary to record, the value is the index, and the array index is the value
for i,num in enumerate(nums):#Enumeration to get the index and value at one time
if hashMap.get(target-num) is not None:#Does the corresponding value exist
return [hashMap.get(target-num), i]#Existence return
hashMap[num] = i#No storage exists
#36 ms 15.9 MB amazing!!
#Advantages: fast, time complexity O (n)
#Disadvantages: it is difficult to understand that space is used for time
2.2 sum of three numbers
Give you an array num containing n integers. Judge whether there are three elements a, b and c in num, so that a + b + c = 0? Please find all triples with sum 0 and no repetition.
Note: the answer cannot contain duplicate triples.
Example 1:
Input: num = [- 1,0,1,2, - 1, - 4]
Output: [- 1, - 1,2], [- 1,0,1]]
Example 2:
Input: num = []
Output: []
Example 3:
Input: num = [0]
Output: []
Tips:
0 <= nums.length <= 3000
-105 <= nums[i] <= 105
Idea: the whole idea is to traverse, find all triples equal to zero, and then de duplicate. However, the time complexity of violent enumeration is too high, so the data is sorted first, and then an element is determined, and the sum of the rest is its negative value.
2.2.1 to solve a double pointer (left and right), sort the data first
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
answer = []
nums.sort()
for i in range(len(nums)):
target = -nums[i]
left = i + 1
right = len(nums) - 1
while(left<right):
sum = nums[left] + nums[right]
if(sum == target):
if([nums[i],nums[left],nums[right]] not in answer):
answer.append([nums[i],nums[left],nums[right]])
left += 1
right -= 1
elif(sum < target):
left += 1
else:
right -= 1
return answer
#3236 ms 17.4 MB
#Advantages: the time complexity is O(n2), which reduces one level of time complexity compared with violent enumeration.
#Disadvantages: slow speed. Various situations were not considered.
2.2.2 various situations of solution II optimization
1. If the array is empty or less than 3, return null directly.
2. When traversing to a positive number, due to data sorting, the sum of the next two will not be 0 and will be returned directly
3. After sorting, the adjacent same numbers will no longer match. The first number will be skipped directly, and the second number will be added by 1. There will be no duplication.
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
n=len(nums)
res=[]
if(not nums or n<3):
return []
nums.sort()
res=[]
for i in range(n):
if(nums[i]>0):
return res
if(i>0 and nums[i]==nums[i-1]):
continue
L=i+1
R=n-1
while(L<R):
if(nums[i]+nums[L]+nums[R]==0):
res.append([nums[i],nums[L],nums[R]])
while(L<R and nums[L]==nums[L+1]):
L=L+1
while(L<R and nums[R]==nums[R-1]):
R=R-1
L=L+1
R=R-1
elif(nums[i]+nums[L]+nums[R]>0):
R=R-1
else:
L=L+1
return res
#640 ms 17.7 MB
#Advantages: fast.
#Disadvantages: consider a variety of situations.
2.3 sum of the nearest three numbers
Give you a length of n integer array nums and a target value target. Please select three integers from nums to make their sum closest to target.
Returns the sum of these three numbers.
It is assumed that there is only exactly one solution for each set of inputs.
Example 1:
Input: num = [- 1,2,1, - 4], target = 1
Output: 2
Explanation: the closest sum to target is 2 (- 1 + 2 + 1 = 2).
Example 2:
Input: num = [0,0,0], target = 1
Output: 0
Tips:
3 <= nums.length <= 1000
-1000 <= nums[i] <= 1000
-104 <= target <= 104
2.3.1 solution: Double finger needles are used to avoid the three cycle of enumeration, or to sort the array first, to see whether the selection is close to the target value, and then adjust the size.
class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
nums.sort()
answer = nums[0] + nums[1] + nums[2]
for i in range(len(nums)):
head = nums[i]
left = i + 1
right = len(nums) - 1
while(left<right):
sum = nums[left] + nums[right] + head
if(abs(sum - target) < abs(answer - target)):
answer = sum
if(sum > target):
right -= 1
elif(sum < target):
left += 1
else:
return answer
return answer
#196 ms 15.3 MB
#Advantages: high speed
#Disadvantages: not very intuitive. First of all, we should understand the routine of double pointer
2.4 removing elements
Give you an array num and a value val. you need to remove all elements with a value equal to Val in place and return the new length of the array after removal.
Instead of using extra array space, you must use only O(1) extra space and modify the input array in place.
The order of elements can be changed. You don't need to consider the elements in the array that exceed the new length.
explain:
Why is the returned value an integer, but the output answer is an array?
Note that the input array is passed by reference, which means that modifying the input array in the function is visible to the caller.
You can imagine the internal operation as follows:
//nums is passed by reference. That is, no copy of the arguments is made
int len = removeElement(nums, val);
//Modifying the input array in the function is visible to the caller.
//According to the length returned by your function, it will print out all elements within that length range in the array.
for (int i = 0; i < len; i++) {
print(nums[i]);
}
Example 1:
Input: num = [3,2,2,3], Val = 3
Output: 2, Num = [2,2]
Explanation: the function should return a new length of 2, and the first two elements in num are 2. You don't need to consider the elements in the array that exceed the new length. For example, if the new length returned by the function is 2, and num = [2,2,3,3] or num = [2,2,0,0], it will also be regarded as the correct answer.
Example 2:
Input: num = [0,1,2,2,3,0,4,2], Val = 2
Output: 5, Num = [0,1,4,0,3]
Explanation: the function should return a new length of 5, and the first five elements in num are 0, 1, 3, 0 and 4. Note that these five elements can be in any order. You don't need to consider the elements in the array that exceed the new length.
Tips:
0 <= nums.length <= 100
0 <= nums[i] <= 50
0 <= val <= 100
2.4.1 solution 1 call python's list function remove to judge whether there is a val and remove to delete
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
while(val in nums):
nums.remove(val)
return len(nums)
#24 ms 14.9 MB
#Advantages: simple implementation and good speed
#Useless algorithmic thinking: it's easy to lose your job (doge)
2.4.2 solution 2 double pointers, we re assign values to the array. left represents the index of the new array. right traverses the old array. If the old array is not deleted, it is assigned to the new array
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
left = 0
for right in range(len(nums)):
if(nums[right]!=val):
nums[left] = nums[right]
left += 1
return left
2.5 delete duplicates in ordered array
Give you an ordered array nums, please delete the repeated elements in place, make each element appear only once, and return the new length of the deleted array.
Do not use additional array space. You must modify the input array in place and complete it with O(1) additional space.
explain:
Why is the returned value an integer, but the output answer is an array?
Note that the input array is passed by reference, which means that modifying the input array in the function is visible to the caller.
You can imagine the following internal operations:
//nums is passed by reference. That is, no copy of the arguments is made
int len = removeDuplicates(nums);
//Modifying the input array in the function is visible to the caller.
//According to the length returned by your function, it will print out all elements within that length range in the array.
for (int i = 0; i < len; i++) {
print(nums[i]);
}
Example 1:
Input: num = [1,1,2]
Output: 2, Num = [1,2]
Explanation: the function should return a new length of 2, and the first two elements of the original array num are modified to 1 and 2. There is no need to consider the elements in the array that exceed the new length.
Example 2:
Input: num = [0,0,1,1,1,2,2,3,3,4]
Output: 5, Num = [0,1,2,3,4]
Explanation: the function should return a new length of 5, and the first five elements of the original array num are modified to 0, 1, 2, 3 and 4. There is no need to consider the elements in the array that exceed the new length.
Tips:
0 <= nums.length <= 3 * 104
-104 <= nums[i] <= 104
nums is arranged in ascending order
2.5.1 solution 1 because of the ordered array, count the consecutive same numbers, and then delete them one by one
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
delete_num = []
for i in range(len(nums)-1):
if(nums[i]==nums[i+1]):
delete_num.append(nums[i])
for i in delete_num:
nums.remove(i)
return len(nums)
#1112 ms 15.8 MB
#Advantages: simple implementation
#The idea of the algorithm is not strong, the speed is slow, and it is easy to lose your job (doge)
2.5.2 solution 2 move elements according to the sequence number. Because it is an ordered array, set the sequence number index from 0 and i from 1. If it is different, the dislocation assignment value remains unchanged. If the dislocation value is the same, continue. The next assignment will cover the last repeated digit. The core idea is that index and i will always be wrong without repetition. If i repeat, i plus 1 will cover the repeated elements.
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
n = len(nums)
index=0
for i in range(1,n):
if nums[index]==nums[i]:
continue
nums[index+1] = nums[i]
index += 1
return index+1
#32 ms 15.9 MB
#Advantages: simple implementation
#Disadvantages: the idea of the algorithm is difficult to understand.