每周完成一个ARTS:
- 每周至少做一个 leetcode 的算法题
- 阅读并点评至少一篇英文技术文章
- 学习至少一个技术技巧
- 分享一篇有观点和思考的技术文章。
(也就是 Algorithm、Review、Tip、Share 简称ARTS)
Algorithm
LeetCode算法题
- Two Sum
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:
1 | Given nums = [2, 7, 11, 15], target = 9, |
两数之和
给定一个整型数组nums和一个目标值target,在数组中找出两个数相加之和等于目标值,返回它们的下标。
可以假设每个目标值只有一个对应的答案,但是你不能使用这个数组中同样的元素两次。
思路:
将数组中每个数和它后面的元素依次相加之和与目标值比较,如果相等就返回这两个值的下标。
Java 程序实现
1 | class Solution { |
复杂度分析:
- 时间复杂度O(n^2)
- 空间复杂度O(1)
LeetCode提供了时间复杂度是O(n)的解决方法,https://leetcode.com/problems/two-sum/solution/
LeetCode 给出的第一种解决方法是类似我上面写的方法,也叫做 Brute Force Approach。
注意,LeetCode 给出的这种方法并没有直接将两个int 值相加,而是使用减法if (nums[j] == target - nums[i])
,为什么这么做呢?
这样可以防止整型溢出!本周ARTS的Share部分分享了一篇关于整型溢出问题,请移步->。
Review
Elasticsearch Getting Started
总结:
Elasticsearch 是一个高扩展的开源的全文搜索和分析引擎,它可以近实时地存储、搜索、分析大量的数据。
Elasticsearch 使用场景
- 网上商城,提供用户搜索产品
- 分析挖掘收集到的日志或交易数据
- 商业智能BI
Tip
使用 Optional 摆脱 NullPointException 的折磨
案例代码
1 | import org.junit.Test; |
Share
分享coolshell上的一篇文章
C语言的整型溢出问题
虽然文章标题是C语言,其中提供的思路不仅限于C语言,文章中提到如何防止整型溢出,值得一读。