@@ -157,9 +157,108 @@ int[] twoSum(int[] nums, int target) {
157
157
158
158
![ labuladong] ( ../pictures/labuladong.jpg )
159
159
160
+ [ labuladong] ( https://github.com/labuladong ) 提供TwoSum I JAVA解法代码:
161
+
162
+ ``` JAVA
163
+ int [] twoSum(int [] nums, int target) {
164
+ int n = nums. length;
165
+ index< Integer , Integer > index = new HashMap<> ();
166
+ // 构造一个哈希表:元素映射到相应的索引
167
+ for (int i = 0 ; i < n; i++ )
168
+ index. put(nums[i], i);
169
+
170
+ for (int i = 0 ; i < n; i++ ) {
171
+ int other = target - nums[i];
172
+ // 如果 other 存在且不是 nums[i] 本身
173
+ if (index. containsKey(other) && index. get(other) != i)
174
+ return new int [] {i, index. get(other)};
175
+ }
176
+
177
+ return new int [] {- 1 , - 1 };
178
+ }
179
+ ```
180
+
181
+ [ Jinglun Zhou] ( https://github.com/Jasper-Joe ) 提供TwoSum I C++解法代码:
182
+
183
+ ``` CPP
184
+ class Solution {
185
+ public:
186
+ vector<int > twoSum(vector<int >& nums, int target) {
187
+ int n=nums.size();
188
+ unordered_map<int,int> index;
189
+ // 构造一个哈希表: 元素映射到相应的索引
190
+ for(int i=0;i<n;i++) // 进行预处理
191
+ index[ nums[ i]] =i; // 当前的元素作为key, 当前的索引作为value
192
+
193
+ for(int i=0;i<n;i++)
194
+ {
195
+ int other=target-nums[ i] ;// 得到能与nums[ i] 相加凑成target的另外那个数
196
+ // 如果other存在且不是nums[ i] 本身
197
+ if(index.count(other) && index[ other] !=i)
198
+ return {i,index[ other] };
199
+ }
200
+
201
+ return {-1,-1};// 如果不存在返回{-1,-1}, 当然根据题意必然存在解
202
+ }
203
+ };
204
+ ```
205
+ [labuladong](https://github.com/labuladong) 提供TwoSum II JAVA解法代码:
206
+
207
+ ```JAVA
208
+ class TwoSum {
209
+ Map<Integer, Integer> freq = new HashMap<>();
210
+
211
+ public void add(int number) {
212
+ // 记录 number 出现的次数
213
+ freq.put(number, freq.getOrDefault(number, 0) + 1);
214
+ }
215
+
216
+ public boolean find(int value) {
217
+ for (Integer key : freq.keySet()) {
218
+ int other = value - key;
219
+ // 情况一
220
+ if (other == key && freq.get(key) > 1)
221
+ return true;
222
+ // 情况二
223
+ if (other != key && freq.containsKey(other))
224
+ return true;
225
+ }
226
+ return false;
227
+ }
228
+ }
229
+ ```
230
+ [Jinglun Zhou](https:// github.com/Jasper-Joe) 提供TwoSum II C++解法代码:
231
+
232
+ ```CPP
233
+ class TwoSum {
234
+ public:
235
+ unordered_map<int,int> freq; // key为当前加入的元素,value为当前加入元素一共出现的频率
236
+ TwoSum() {} // constructor
237
+
238
+ void add(int number) {
239
+ // 记录number出现的次数
240
+ freq[number]++;
241
+ }
242
+
243
+ bool find (int value) {
244
+ for(auto& cur: freq )
245
+ {
246
+ int other=value-cur.first;
247
+ // 情况一: other和当前这个元素一样大,所以需要两个这个的元素才能构成value
248
+ if(other==cur.first && cur.second>1)
249
+ return true;
250
+ // 情况二: other和当前这个元素不一样,other在freq中需要至少出现一次,与twoSum I道理一样
251
+ if(other!=cur.first && freq.count(other))
252
+ return true;
253
+ }
254
+ return false;
255
+ }
256
+ };
257
+ ```
258
+
160
259
161
260
[上一篇:滑动窗口技巧](../算法思维系列/滑动窗口技巧.md)
162
261
163
262
[下一篇:常用的位操作](../算法思维系列/常用的位操作.md)
164
263
165
- [ 目录] ( ../README.md#目录 )
264
+ [目录](../README.md#目录)
0 commit comments