首页 > 其他分享 >lc1(暴力、哈希)

lc1(暴力、哈希)

时间:2024-04-26 13:55:24浏览次数:17  
标签:right return target nums int lc1 num 哈希 暴力

给定一个整数数组 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 <= 104
  • -109 <= nums[i] <= 109
  • -109 <= target <= 109
  • 只会存在一个有效答案

 1、暴力法

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

时间复杂度O(n2)

2、哈希表

1 class Solution:
2     def twoSum(self, nums: List[int], target: int) -> List[int]:
3         dir = {}
4         for index, num in enumerate(nums):
5             if num not in dir:
6                 dir[target - num] = index
7             else:
8                 return [dir[num], index]
9         return []

时间复杂度O(n)

3、双指针(错误)

 1         left = 0
 2         right = len(nums) - 1
 3         while left < right:
 4             if nums[left] + nums[right] == target:
 5                 return [left, right]
 6             elif nums[left] + nums[right] < target:
 7                 left += 1
 8             else:
 9                 right -= 1
10         return []
双指针,因为数组无序,不能用双指针。使用双指针,需要排序,但排序后数组的索引也会改变,所以不行  

 

进阶:你可以想出一个时间复杂度小于 O(n2) 的算法吗?

 

标签:right,return,target,nums,int,lc1,num,哈希,暴力
From: https://www.cnblogs.com/zxc5612301/p/18159926

相关文章

  • 【Redis】Redis的操作命令(二)——Redis 哈希(HASH)
    Redishash是一个string类型的field(字段)和value(值)的映射表,hash特别适合用于存储对象。当设置一个名为demo的哈希对象时:HSETdemoname"redistutorial"description"redisbasiccommandsforcaching"likes20visitors23000 获取哈希对象语句,如下:HGETALLde......
  • 2024-04-23---简单题---有效的字母异位词(哈希表)
    题目:思路:排序:复杂度较高。两个字符串进行排序,然后开始比较两个字符串是否相等哈希表:主要是一个hashmap记录第一个字符串所有字符出现的次数,然后遍历第二个字符串没找到一个就将次数减一。看最后所有的值是否为0.时间复杂度选第二种,简单题罢了。代码:排序classSolution......
  • 异或哈希
    问题:https://codeforces.com/contest/1175/problem/F关键点:随机化+异或1.为何要异或:忽略顺序将1~n随机的一一映射到longlong值域内,形成新的映射数组b。再根据异或的特点,只需要判断:b[1]⊕b[2]⊕…………⊕b[n]==b[a[l]]⊕b[a[l+1]]⊕……⊕b[a[r]]2.为何要随机,因为若不随......
  • 哈希
    哈希入门LeetCode1.两数之和注意添加顺序,先判断再添加...classSolution{publicint[]twoSum(int[]nums,inttarget){//{numsvalue:index}Map<Integer,Integer>map=newHashMap<>();List<Integer>res=newArrayList<>......
  • MD5哈希长度延展攻击
    MD5哈希长度延展攻击原理已知原始消息(m)和其对应的哈希值(h)。选择额外数据(m’)。计算填充,使得填充后的消息长度满足长度模512等于448,并包含新消息的长度信息。构造新消息(m+\text{填充}+m’)。计算新消息的哈希值(h’)。代码importhas......
  • 928. 尽量减少恶意软件的传播 II【并查集加暴力删边判断】
    题意不是很清晰:1.比如对于graph=[[1,1,0],[1,1,1],[0,1,1]],initial=[0,1]来说,可以发现结点的链接情况是0-1-2,感染源结点是0和1,若是按之前题目的要求,移除0和1都不会减少最终感染个数,但是应该返回结点0,因为其index小。但是应用此题的条件,就一定要返回结点1,因为移除结点1之......
  • 哈希
    简介哈希是一种能把字符串(实际上数组也行,不过本文都会以字符串为例)映射成一个数的算法,哈希就是把一个字符串转成一个\(K\)进制数,但由于得到的数可能会非常大,所以其中会用到取模,因此哈希也有些玄学(建议CF有赛后hack的比赛不要使用哈希,或提高哈希的安全度)。普通哈希可以将......
  • MD5哈希长度延展攻击(选做)
    任务描述:在一个使用MD5哈希算法的系统中,管理员使用了一个密钥k和命令cmd的组合来生成每个命令的签名:hash(k||cmd)。你已经获得了一个允许查看文件的命令cmd=viewfile和对应的签名h,但你希望通过哈希长度延展攻击,生成一个新的签名,该签名能够让你执行删除文件的命令(删除文件的命令为......
  • MD5哈希长度延展攻击(选做)
    MD5哈希长度延展攻击(选做)任务任务描述:在一个使用MD5哈希算法的系统中,管理员使用了一个密钥k和命令cmd的组合来生成每个命令的签名:hash(k||cmd)。你已经获得了一个允许查看文件的命令cmd=viewfile和对应的签名h,但你希望通过哈希长度延展攻击,生成一个新的签名,该签名能够让你执行......
  • MD5哈希长度延展攻击
    任务描述:在一个使用MD5哈希算法的系统中,管理员使用了一个密钥k和命令cmd的组合来生成每个命令的签名:hash(k||cmd)。你已经获得了一个允许查看文件的命令cmd=viewfile和对应的签名h,但你希望通过哈希长度延展攻击,生成一个新的签名,该签名能够让你执行删除文件的命令(删除文件的命令为......