java算法学习(力扣-两数之和)

题目来自于力扣，内容目的-更多的是自己学习的记载
1. 两数之和

给定一个整数数组 nums 和一个整数量标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案，并且你不能利用两次相同的元素。
你可以按任意顺序返回答案。

示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：由于 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]


提示：

• 2 <= nums.length <= 10(4)
  
• -10(9) <= nums <= 10(9)
  
• -10(9) <= target <= 10(9)
  
• 只会存在一个有效答案
  

进阶：你可以想出一个时间复杂度小于 O(n(2)) 的算法吗？


个人解法

思路：双层循环，找到符合条件的情况O(n(2))

1. class Solution {
2.     public int[] twoSum(int[] nums, int target) {
3.         for(int i=0;i<nums.length;i++){
4.             for(int j=i+1;j<nums.length;j++){
5.                 if(nums[i]+nums[j]==target ){
6.                     int [] a={i,j};
7.                     return a;
8.                 }
9.             }
10.         }
11.       return new int[0];
12.     }
13. }

复制代码

进阶解法

官方题解1. 两数之和 - 力扣（LeetCode）

1. class Solution {
2.     public int[] twoSum(int[] nums, int target) {
3.         int n = nums.length;
4.         HashMap<Integer, Integer> hashtable = new HashMap<>();
5.         for (int i = 0; i < n; i++) {
6.             if(hashtable.containsKey(target - nums[i]))//别漏了s，别忘记大写K，别忘记num+s
7.             {
8.                 return new int[]{hashtable.get(target - nums[i]), i};
9.             }
10.             hashtable.put(nums[i], i);
11.             //先判断有是否满足条件，再存储，减少开销
12.             //以{键，值}存储
13.         }
14.         return new int[0];
15.     }
16. }

复制代码

学习：

HashMap 是 Java 中一个非经常用的集合类，它用于存储键值对，并允许通过键快速查找对应的值。它黑白同步的，因此在多线程环境下大概需要额外的同步处置处罚。
下面是 HashMap 中一些常用的函数，并附带了示例代码：
1. put(K key, V value)

• 功能：将指定的键值对插入到哈希表中。如果该键已经存在，则更新其对应的值。
  
• 时间复杂度：平均为 O(1)，最坏情况下为 O(n)（当哈希表出现严厉冲突时）。
  

示例：

1. HashMap<String, Integer> map = new HashMap<>();
2. map.put("apple", 10);
3. map.put("banana", 20);
4. System.out.println(map);  // 输出: {apple=10, banana=20}

复制代码

 
2. get(Object key)

• 功能：返回指定键对应的值。如果键不存在，返回 null。
  
• 时间复杂度：平均为 O(1)，最坏情况下为 O(n)。
  

示例：

1. HashMap<String, Integer> map = new HashMap<>();
2. map.put("apple", 10);
3. map.put("banana", 20);
4. System.out.println(map.get("apple"));  // 输出: 10
5. System.out.println(map.get("orange")); // 输出: null

复制代码

 
3. containsKey(Object key)

• 功能：检查哈希表中是否包含指定的键。
  
• 时间复杂度：平均为 O(1)，最坏情况下为 O(n)。
  

示例：

1. HashMap<String, Integer> map = new HashMap<>();
2. map.put("apple", 10);
3. map.put("banana", 20);
4. System.out.println(map.containsKey("apple"));  // 输出: true
5. System.out.println(map.containsKey("orange")); // 输出: false

复制代码

4. containsValue(Object value)

• 功能：检查哈希表中是否包含指定的值。
  
• 时间复杂度：O(n)，由于需要遍历哈希表中的全部值。
  

示例：

1. HashMap<String, Integer> map = new HashMap<>();
2. map.put("apple", 10);
3. map.put("banana", 20);
4. System.out.println(map.containsValue(10));  // 输出: true
5. System.out.println(map.containsValue(30));  // 输出: false

复制代码

5. remove(Object key)

• 功能：删除哈希表中指定的键及其对应的值。如果该键不存在，什么都不做。
  
• 时间复杂度：平均为 O(1)，最坏情况下为 O(n)。
  

示例：

1. HashMap<String, Integer> map = new HashMap<>();
2. map.put("apple", 10);
3. map.put("banana", 20);
4. map.remove("apple");
5. System.out.println(map);  // 输出: {banana=20}

复制代码

6. size()

• 功能：返回哈希表中键值对的数量。
  
• 时间复杂度：O(1)。
  

示例：

1. HashMap<String, Integer> map = new HashMap<>();
2. map.put("apple", 10);
3. map.put("banana", 20);
4. System.out.println(map.size());  // 输出: 2

复制代码

7. isEmpty()

• 功能：检查哈希表是否为空（即没有任何键值对）。
  
• 时间复杂度：O(1)。
  

示例：

1. HashMap<String, Integer> map = new HashMap<>();
2. System.out.println(map.isEmpty());  // 输出: true
3. map.put("apple", 10);
4. System.out.println(map.isEmpty());  // 输出: false

复制代码

8. clear()

• 功能：清空哈希表中的全部键值对。
  
• 时间复杂度：O(n)，需要遍历全部元素。
  

示例：

1. HashMap<String, Integer> map = new HashMap<>();
2. map.put("apple", 10);
3. map.put("banana", 20);
4. map.clear();
5. System.out.println(map);  // 输出: {}

复制代码

9. keySet()

• 功能：返回哈希表中全部键的集合（Set<K>）。
  
• 时间复杂度：O(n)，由于需要遍历哈希表中的全部键。
  

示例：

1. HashMap<String, Integer> map = new HashMap<>();
2. map.put("apple", 10);
3. map.put("banana", 20);
4. Set<String> keys = map.keySet();
5. System.out.println(keys);  // 输出: [apple, banana]

复制代码

10. values()

• 功能：返回哈希表中全部值的集合（Collection<V>）。
  
• 时间复杂度：O(n)，由于需要遍历哈希表中的全部值。
  

示例：

1. HashMap<String, Integer> map = new HashMap<>();
2. map.put("apple", 10);
3. map.put("banana", 20);
4. Collection<Integer> values = map.values();
5. System.out.println(values);  // 输出: [10, 20]

复制代码

11. entrySet()

• 功能：返回哈希表中全部键值对的集合（Set<Map.Entry<K, V>>），此中每个元素是一个 Map.Entry 对象，包含一个键和一个值。
  
• 时间复杂度：O(n)，由于需要遍历哈希表中的全部键值对。
  

示例：

1. HashMap<String, Integer> map = new HashMap<>();
2. map.put("apple", 10);
3. map.put("banana", 20);
4. Set<Map.Entry<String, Integer>> entries = map.entrySet();
5. for (Map.Entry<String, Integer> entry : entries) {
6.     System.out.println(entry.getKey() + " = "entry.getValue());
7. }
8. // 输出:// apple = 10// banana = 20

复制代码

12. putIfAbsent(K key, V value)

• 功能：如果哈希表中不包含指定的键，则插入该键值对。如果键已存在，则不做任何操纵。
  
• 时间复杂度：O(1)（平均情况）。
  

示例：

1. HashMap<String, Integer> map = new HashMap<>();
2. map.put("apple", 10);
3. map.putIfAbsent("banana", 20);  // 插入 "banana" = 20
4. map.putIfAbsent("apple", 30);    // "apple" 已经存在，值不会更新
5. System.out.println(map);  // 输出: {apple=10, banana=20}

复制代码

13. replace(K key, V value)

• 功能：如果哈希表中包含指定的键，则用新值更换其对应的旧值。如果键不存在，则不做任何操纵。
  
• 时间复杂度：O(1)（平均情况）。
  

示例：

1. HashMap<String, Integer> map = new HashMap<>();
2. map.put("apple", 10);
3. map.replace("apple", 15);  // 更新 "apple" 的值为 15
4. System.out.println(map);  // 输出: {apple=15}

复制代码

总结

HashMap 提供了很多方法来处置处罚键值对的操纵，包括添加、查找、删除、更新、检查等。这些方法通常具有 O(1) 的时间复杂度，允许高效地进行查找和插入操纵。

• 常用方法：
  
  
  
  • put(), get(), containsKey(), remove(), size(), clear()
    
  • keySet(), values(), entrySet()
    
  • putIfAbsent(), replace()
    
  
  

HashMap 黑白常强大的数据布局，适用于需要频繁查找、更新和插入数据的场景。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。