# LeetCode | Data Structure I | 14 Days Challenge | Day 1-2
###### tags: `LeetCode` `Data Structure I` `14 Days Challenge`
## Day 1
### [217. Contains Duplicate](https://leetcode.com/problems/contains-duplicate/?envType=study-plan&id=data-structure-i)
### 題目敘述
> *Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.*
### 測資
:::info
Input: nums = [1,2,3,1]
Output: true
:::
:::info
Input: nums = [1,2,3,4]
Output: false
:::
:::info
Input: nums = [1,1,1,3,3,4,3,2,4,2]
Output: true
:::
### 數值範圍
1 <= nums.length <= 10^5^
-10^9^ <= nums\[i] <= 10^9^
### 核心概念
==map、unordered_map==
### 想法
**每個數字至少出現兩次**，很明顯就是Map XD，建議用unordered_map加快runtime。
***time : 3~5 mins
time complexity : $O(n)$
space complexity : $O(n)$***
### 程式碼
```c++=1
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
unordered_map <int,int> map;
bool flag = false;
for(int i=0;i<nums.size();i++){
if(!map[nums[i]])
map[nums[i]] = 1;
else{
flag = true;
break;
}
}
return flag;
}
};
```
### [53. Maximum Subarray](https://leetcode.com/problems/maximum-subarray/?envType=study-plan&id=data-structure-i)
### 題目敘述
> *Given an integer array nums, find the
subarray
with the largest sum, and return its sum.*
### 測資
Example 1:
:::info
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The subarray [4,-1,2,1] has the largest sum 6.
:::
Example 2:
:::info
Input: nums = [1]
Output: 1
Explanation: The subarray [1] has the largest sum 1.
:::
Example 3:
:::info
Input: nums = [5,4,-1,7,8]
Output: 23
Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.
:::
### 數值範圍
1 <= nums.length <= 10^5^
-10^4^ <= nums\[i] <= 10^4^
### 核心概念
==DP==
### 想法
由於數字不侷限於正整數，因此每次判斷nums\[j]~nums\[i-1](前面數字的總和)加上nums\[i](當下的數字)，是否會小於nums\[i]，若小於，前面的數值比目前的數值還小，**不如放棄抓取**，最後判斷上一個最大值(result)和目前最大值(cur)誰更大。
我超不會解DP啊啊啊！資質駑鈍QQ
***time : 20~30 mins
time complexity : $O(n)$
space complexity : $O(1)$***
### 程式碼
```c++=1
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int len = nums.size();
int cur = 0, result = -1e9;
if(len == 1) return nums[0];
for(int i=0;i<len;i++){
cur += nums[i];
if(cur < nums[i]) cur = nums[i];
if(cur > result) result = cur;
}
return result;
}
};
```
## Day 2
### [1. Two Sum](https://leetcode.com/problems/two-sum/?envType=study-plan&id=data-structure-i)
### 題目敘述
>*Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.*
>*You may assume that each input would have exactly one solution, and you may not use the same element twice.*
>*You can return the answer in any order.*
### 測資
Example 1:
:::info
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
:::
Example 2:
:::info
Input: nums = [3,2,4], target = 6
Output: [1,2]
:::
Example 3:
:::info
Input: nums = [3,3], target = 6
Output: [0,1]
:::
### 核心概念
==map、unordered_map==
### 數值範圍
2 <= nums.length <= 10^4^
-10^9^ <= nums\[i] <= 10^9^
-10^9^ <= target <= 10^9^
**Only one valid answer exists.**
### 想法
一樣用map解！EZ
***time : 10 mins
time complexity : $O(n)$
space complexity : $O(n)$***
### 程式碼
```c++=1
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int,int> mp;
vector<int> ans(2);
int len = nums.size();
for (int i = 0; i < len; i++) {
if (mp.find(target - nums[i]) == mp.end())
mp[nums[i]] = i;
else {
ans[0] = mp[target - nums[i]];
ans[1] = i;
}
}
return ans;
}
};
```
### [88. Merge Sorted Array](https://leetcode.com/problems/merge-sorted-array/?envType=study-plan&id=data-structure-i)
### 題目敘述
>*You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.*
>*Merge nums1 and nums2 into a single array sorted in non-decreasing order.*
>*The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.*
### 測資
Example 1:
:::info
Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
Explanation: The arrays we are merging are [1,2,3] and [2,5,6].
The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.
:::
Example 2:
:::info
Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]
Explanation: The arrays we are merging are [1] and [].
The result of the merge is [1].
:::
Example 3:
:::info
Input: nums1 = [0], m = 0, nums2 = [1], n = 1
Output: [1]
Explanation: The arrays we are merging are [] and [1].
The result of the merge is [1].
Note that because m = 0, there are no elements in nums1. The 0 is only there to ensure the merge result can fit in nums1.
:::
### 核心概念
==array==
### 數值範圍
nums1.length == m + n
nums2.length == n
0 <= m, n <= 200
1 <= m + n <= 200
-10^9^ <= nums1[i], nums2[j] <= 10^9^
### 想法
當初沒什麼好想法XD，參考了留言區大佬的解法，分享給大家~
因為n1.length=m+n，因此題目是希望我們在原有的陣列上直接做merge的動作。
利用三個指標(n1_p, n2_p, n1_end)，n1_p指到nums\[1]**數字不為0的最後一位上**，n2_p指到nums\[2]最後一位上，n1_end指到nums\[1]的最後一位上，從陣列後面開始做判斷和賦值的動作。
如圖: 記得每次做完都會將指標-1，因此圖沒畫出來，不然要畫好多張圖XD。
***time : 20 mins
time complexity : $O(m+n)$
space complexity : $O(1)$
(m : nums1.length, n : nums2.length)***
### 程式碼
```c++=1
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int n1_p = m - 1, n2_p = n - 1, n_end = m + n - 1;
while(n2_p >= 0){
if(n1_p >= 0 && nums1[n1_p] >= nums2[n2_p]){
nums1[n_end--] = nums1[n1_p--];
}
else{
nums1[n_end--] = nums2[n2_p--];
}
}
}
};
```
Sign in with Wallet
Connect another wallet