1、數組
- 數組是由相同類型的元素組成的數據集合，并且占據一塊連續的內存，按照順序存儲數據。
1.1、數組的特性：
- 數組元素通過下標獲取數據
- 數組對象初始化時，需要先指定數組容量大小，并根據容量大小分配內存。
- 缺點：需要為所有的數據預先分配內存，可能存在空閑的區域沒有得到充分利用。
1.2、動態數組
- 先為數組分配較小的內存空間，然后在需要的時候，在數組中添加新的數據。
- 當容量不足時，需要重新分配一塊更大的空間，要把之前的數據復制到新的數組中，再把之前的內存釋放。
- 缺點：數據拷貝時，需要進行大量的額外操作。
2、指針
- 能定位數據容器中（也就是內存中）某個數據的手段。也就是數據的句柄或者地址。
2.1、雙指針
- 雙指針是一種解題方法
- 方向相反的雙指針經常用來求排序數組中的兩個數字之和。通常分別指向數組的首位兩端，根據結果值對兩端的指針進行向中間移動。
- 方向相同的雙指針通常用來求正數數組中子數組的和或乘積。
3、LCR 006 兩數之和
3.1、題目信息：
- https://leetcode.cn/problems/kLl5u1/description/
給定一個已按照 升序排列 的整數數組 numbers ，請你從數組中找出兩個數滿足相加之和等于目標數 target 。
函數應該以長度為 2 的整數數組的形式返回這兩個數的下標值。numbers 的下標 從 0 開始計數 ，所以答案數組應當滿足 0 <= answer[0] < answer[1] < numbers.length 。
假設數組中存在且只存在一對符合條件的數字，同時一個數字不能使用兩次。示例 1：
輸入：numbers = [1,2,4,6,10], target = 8
輸出：[1,3]
解釋：2 與 6 之和等于目標數 8 。因此 index1 = 1, index2 = 3 。示例 2：
輸入：numbers = [2,3,4], target = 6
輸出：[0,2]示例 3：
輸入：numbers = [-1,0], target = -1
輸出：[0,1]
3.2、解題思路
- 輸入一個整數數組和一個目標整數，要求從數組中找出兩個數，要求他們的和等于目標整數，返回兩個元素的下標數組
1）、暴力解法
- 雙層for循環，遍歷數組獲得整數元素，然后遍歷其他元素，判斷他們的和是否等于目標值
- 時間復雜度n的平方，沒有使用到數組元素是升序排序的特性
- 代碼簡單，不實現
2）、哈希表解法
- 遍歷數組元素，遍歷的過程中，判斷目標值與遍歷元素的差值，判斷差值是否在哈希表中，如果存在則返回下標數組
- 如果不存在，則將當前遍歷的元素和下標值，保存到哈希表中
vector<int> twoSum(vector<int> &numbers, int target)
{vector<int> res;std::map<int, int> map;for (int i = 0; i < numbers.size(); i++){int num = target - numbers[i];if (map.find(num) != map.end()) {res.push_back(map[num]);res.push_back(i);break;}map[numbers[i]] = i;}return res;
}
3）、雙指針解法
- 定義兩個下標，從數組的兩端開始往中間遍歷
- 如果遍歷到的兩個元素的和等于目標值，則直接返回，如果兩元素和大于目標值，則right角標左移，否則left角標右移
vector<int> twoSum(vector<int> &numbers, int target)
{vector<int> res;int left = 0;int right = numbers.size() - 1;while (left < right && target != (numbers[left] + numbers[right])){if (numbers[left] + numbers[right] < target){left++;}else{right--;}}res.push_back(left);res.push_back(right);return res;
}
4、總結
- 數組特性，具有相同數據類型的數據集合，在內存中按順序連續存儲，數組對象就是數據的指針，可通過下標獲取到數組中元素的值
- 數組優缺點：可通過數組索引下標直接獲取元素值，在數組尾部添加數據，插入與刪除數據需要進行數據移動； 數組使用前需要預先分配內存，有可能有些內存沒有使用到。
- 動態內存，剛開始分配一個小容量的內存，當數據量增加時進行擴容，需要將原數據拷貝到新的數組中。
- 指針概念，就是可以從內存中獲取數據的方式
- 雙指針，是一種解題思路，分為相向指針和相反指針。
- map數據結構使用，查找是否存在某個值使用find方法
)
