---
# System prepended metadata

title: LeetCode | Data Structure I | 14 Days Challenge | Day 1-2
tags: [Data Structure I, LeetCode, 14 Days Challenge]

---

# 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。

![](https://i.imgur.com/LALjfpO.png)


***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--];
            }
        }
    }
};
```
