Algorithm
两数之和:
给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
public int[] twoSum(int[] nums, int target) {
// 解法一:暴力法
int res []=new int[2];
for (int i=0 ; i<nums.length-1; i++){
for (int j = i +1; j<nums.length; j++){
if (nums[i]+nums[j] == target){
res[0] = I;
res[1] = j;
return res;
}
}
}
return res;
// 解法二 : hashmap
Map<Integer,Integer> map = new HashMap<Integer,Integer>();
for (int i=0 ; i<nums.length; i++){
if (map.containsKey(target - nums[i])){
return new int[]{map.get(target - nums[i]),I};
}
map.put(nums[i], i);
}
throw new IllegalArgumentException("No two sum solution”);
}
Review
Data Structures and Algorithms - Arrays
数组是一个容器,可以存储相同类型固定长的item。大部分数据结构使用数组实现算法。下面是一些重要的点,帮助理解数据的概念:
- 元素 - 存储在数据中的每个item。
- 下标 - 每个元素在数组中的位置都有一个唯一的数字下标标识这个元素。
数组表现
数组可以被不同语言用不同方式定义。如图,让我们用C语言定义数组。
如上图,下面是是一些需要重点注意的点:
- 下标从0开始
- 数组长度是10,意味着它能存储10个元素。
- 每个元素都可以通过下标被访问到。如:我们获取一个下标为6元素的值是9.
基本操作
下列操作支撑一个数组的基本操作:
- 遍历 - 一个一个地打印数组中所有元素
- 插入 - 在指定下标上添加一个元素
- 删除 - 删除指定下标的元素
- 查询 - 使用给定的下标或元素值查询对应的元素
-
更新 - 修改指定下标的元素
在C语,当一个数组被初始化固定长度的数组,每个元素的默认值按下表的顺序。
Tip
近期打算回顾缓存系统:
为什么要使用缓存系统?
随着应用系统数据量的增大,访问人数的增加,但访问速度不能下降的现象,我们需要有更好的办法来应对,缓存系统算是所有办法中最常使用的,在各类系统设计中都会考虑并使用,它也被叫做硬盘存储的加速器。
- 硬件加速
- 物理加速
- 软件加速
先看下硬件方面的加速,L1>L2>L3,内存,SSD,SATA ...
从下列几点说明硬件加速的概念:
- 内存(RAM)使用寄生电容充放电来表示0和1,断电后电容放电,数据就消失了。
- SSD和SATA(ROM)用MOS管中间的一个绝缘体来储备电子,可以长期保存。
- 在通常下,各硬件的读写速度:L1>L2>L3 > 内存 > SSD >SATA
- 内存四通道DDR3-2400工作在1T模式下,内存读写速度也只有43GB/S左右
- SSD读写大约都在 0.5G/s(500M/s)
- L1大约500-800G/s
不同的品牌不同型号读写速度会有比较大的差异,但量级不会变。
Share
在写文章时,如何更规范使用标点符号,本周分享标点符号国家标准。
标点符号标准