問題描述：
Given an array of integers, return indices of the two numbers such that they add up to a specific target.You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
c++解決：
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> a(2);
for(int i=0;i<nums.size();i++)
for(int j=i+1;j<nums.size();j++)
if(nums[i]+nums[j]==target)
{
a[0]=i;
a[1]=j;
return a;
}
return a;
}
};
時間復雜度 O(n^2)
- c++引用的作用梅割？
答：c中有傳值和傳址兩種方式坐桩。傳值方式，函數(shù)調用過程中生成一個臨時變量的形參微酬，把實參的值傳遞給形參，實參的值在過程中不會被改變。而傳址方式會可以改變實參的值。因為指針不安全棒妨，c++中引入了“引用”這一概念。
引用就是給對象起了個別名含长，編譯器不會為對象開辟新的內(nèi)存空間，原變量和引用公用一塊內(nèi)存空間伏穆。 - 引用和指針的區(qū)別
引用必須初始化拘泞，沒有空引用，只有空指針枕扫。
int**
int&&右值引用 - 什么是左值陪腌，什么是右值？
左值：有地址空間，可被引用的數(shù)據(jù)對象诗鸭∪敬兀可以取地址。
int s=10;
int &n=s;
右值：只有臨時地址强岸。不可以取地址锻弓。
int &&n=10;
a++是先取出持久對象a的一份拷貝，再使持久對象a的值加1蝌箍，最后返回那份拷貝青灼，而那份拷貝是臨時對象（不可以對其取地址），故其是右值妓盲；
++a則是使持久對象a的值加1杂拨，并返回那個持久對象a本身（可以對其取地址），故其是左值悯衬；
java解決方案：
//時間復雜度O(N),空間復雜度O(n)
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement)) {
return new int[] { map.get(complement), i };
}
map.put(nums[i], i);
}
throw new IllegalArgumentException("No two sum solution");
}
java中的內(nèi)存機制弹沽。
1.棧內(nèi)存和堆內(nèi)存
棧：存放局部變量。
堆：儲存程序員申請的內(nèi)存空間筋粗。也就是new出來的空間贷币。
2.關于HashMap的時間復雜度O(1)的思考
最理想情況西hashmao時間復雜度為O(1)，如果太差時間復雜度為O(n).
常用數(shù)據(jù)結構的時間復雜度
| Data Structure | Add | Find | Delete | GetByIndex |
|---|---|---|---|---|
| Array (T[]) | O(n) | O(n) | O(n) | O(1) |
| Linked list (LinkedList<T>) | O(1) | O(n) | O(n) | O(n) |
| Resizable array list (List<T>) | O(1) | O(n) | O(n) | O(1) |
| Stack (Stack<T>) | O(1) | - | O(1) | - |
| Queue (Queue<T>) | O(1) | - | O(1) | - |
| Hash table (Dictionary<K,T>) | O(1) | O(1) | O(1) | - |
| Tree-based dictionary(SortedDictionary<K,T>) | O(log n) | O(log n) | O(log n) | - |
| Hash table based set (HashSet<T>) | O(1) | O(1) | O(1) | - |
| Tree based set (SortedSet<T>) | O(log n) | O(log n) | O(log n) | - |
